{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Super Palindromes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #enumeration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #枚举"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: superpalindromesInRange"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #超级回文数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>如果一个正整数自身是回文数，而且它也是一个回文数的平方，那么我们称这个数为超级回文数。</p>\n",
    "\n",
    "<p>现在，给定两个正整数&nbsp;<code>L</code> 和&nbsp;<code>R</code> （以字符串形式表示），返回包含在范围 <code>[L, R]</code> 中的超级回文数的数目。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>L = &quot;4&quot;, R = &quot;1000&quot;\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：\n",
    "</strong>4，9，121，以及 484 是超级回文数。\n",
    "注意 676 不是一个超级回文数： 26 * 26 = 676，但是 26 不是回文数。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li><code>1 &lt;= len(L) &lt;= 18</code></li>\n",
    "\t<li><code>1 &lt;= len(R) &lt;= 18</code></li>\n",
    "\t<li><code>L</code> 和&nbsp;<code>R</code>&nbsp;是表示&nbsp;<code>[1, 10^18)</code>&nbsp;范围的整数的字符串。</li>\n",
    "\t<li><code>int(L) &lt;= int(R)</code></li>\n",
    "</ol>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [super-palindromes](https://leetcode.cn/problems/super-palindromes/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [super-palindromes](https://leetcode.cn/problems/super-palindromes/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"4\"\\n\"1000\"', '\"1\"\\n\"2\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def f(a):\n",
    "    a = str(a)\n",
    "    n = len(a)\n",
    "    i , j = 0, n-1\n",
    "    while i<j:\n",
    "        if a[i] != a[j]:\n",
    "            return False\n",
    "        i+=1\n",
    "        j-=1\n",
    "    return True\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        l,r,res = int(left), int(right),0\n",
    "        \n",
    "        for k in range(1,10**5):\n",
    "            sk = str(k)\n",
    "            n = len(sk)\n",
    "            s1 = int(sk+\"\".join(sk[n-1-i] for i in range(n)))\n",
    "            s2 = int(sk+\"\".join(sk[n-1-i] for i in range(1,n)))\n",
    "            s1*=s1\n",
    "            s2*=s2\n",
    "            if s1>=l and s1<=r and f(s1):\n",
    "                res += 1\n",
    "            if s2>=l and s2<=r and f(s2):\n",
    "                res += 1\n",
    "            if s2>r:\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        def check(st):\n",
    "            if st != st[::-1]:\n",
    "                return False\n",
    "            sr = str(int(st)**2)\n",
    "            return sr == sr[::-1]\n",
    "\n",
    "\n",
    "        res = set()\n",
    "        for num in range(1, 10000):\n",
    "            st = str(num)\n",
    "\n",
    "            cur = st\n",
    "            if check(cur):\n",
    "                res.add(int(cur) ** 2)\n",
    "\n",
    "            cur = st + st[::-1]\n",
    "            if check(cur):\n",
    "                res.add(int(cur) ** 2)\n",
    "\n",
    "            for d in range(10):\n",
    "                cur = f\"{st}{d}{st[::-1]}\"\n",
    "                if check(cur):\n",
    "                    res.add(int(cur)**2)\n",
    "\n",
    "        res = sorted(list(res))\n",
    "        return bisect.bisect_right(res, int(right)) - bisect.bisect_left(res, int(left))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        L, R = int(left), int(right)\n",
    "        MAGIC = 100000\n",
    "\n",
    "        def reverse(x):\n",
    "            ans = 0\n",
    "            while x:\n",
    "                ans = 10 * ans + x % 10\n",
    "                x //= 10\n",
    "            return ans\n",
    "        \n",
    "        def is_palindrome(x):\n",
    "            return x == reverse(x)\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        for k in range(MAGIC):\n",
    "            s = str(k)\n",
    "            t = s + s[-2::-1]\n",
    "            v = int(t) ** 2\n",
    "            if v > R: \n",
    "                break\n",
    "            if v >= L and is_palindrome(v):\n",
    "                ans += 1\n",
    "        \n",
    "        for k in range(MAGIC):\n",
    "            s = str(k)\n",
    "            t = s + s[::-1]\n",
    "            v = int(t) ** 2\n",
    "            if v > R: \n",
    "                break\n",
    "            if v >= L and is_palindrome(v):\n",
    "                ans += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        lval, rval = int(left), int(right)\n",
    "        def get(st):\n",
    "            ret, val = 0, 1\n",
    "            while True:\n",
    "                s = str(val)\n",
    "                if st == 0: s1 = s + s[::-1]\n",
    "                else: s1 = s + s[:-1][::-1]\n",
    "                tmp = int(s1)\n",
    "                res = tmp * tmp\n",
    "                val += 1\n",
    "                if res > rval: break\n",
    "                if res < lval: continue\n",
    "                s2 = str(res)\n",
    "                if s2 == s2[::-1]: ret += 1\n",
    "            return ret\n",
    "        return get(0) + get(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        def valid_palind(s: int):\n",
    "            s = str(s)\n",
    "            l, r = 0, len(s)-1\n",
    "            while l < r:\n",
    "                if s[l] != s[r]:\n",
    "                    return False\n",
    "                l += 1\n",
    "                r -= 1\n",
    "            return True\n",
    "        \n",
    "        count = 0\n",
    "        i = 1\n",
    "        seen = set()\n",
    "        while i < 10 ** 5:\n",
    "            tmp = i\n",
    "            j = 0\n",
    "            w = 0\n",
    "            while tmp:\n",
    "                j = j * 10 + tmp % 10\n",
    "                tmp = tmp // 10\n",
    "                w += 1\n",
    "            x1 = i * (10 ** w) + j\n",
    "            x2 = i * (10 ** (w-1)) + j % (10 ** (w-1))\n",
    "\n",
    "            if x1 ** 2 >= int(left) and x1 ** 2 <= int(right) and valid_palind(x1 ** 2) and (x1 ** 2) not in seen:\n",
    "                seen.add(x1 ** 2)\n",
    "                count += 1\n",
    "            if x2 ** 2 >= int(left) and x2 ** 2 <= int(right) and valid_palind(x2 ** 2) and (x2 ** 2) not in seen:\n",
    "                seen.add(x2 ** 2)\n",
    "                count += 1\n",
    "            if x2 ** 2 >= int(right):\n",
    "                break\n",
    "            i += 1\n",
    "        return count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        L, R = int(left), int(right)\n",
    "        MAGIC = 100000\n",
    "\n",
    "        # def reverse(k: int):\n",
    "        #     ans = 0\n",
    "        #     while k:\n",
    "        #         ans = ans * 10 + k % 10\n",
    "        #         k //= 10\n",
    "        #     return ans\n",
    "        \n",
    "        def is_palindrome(x: str):\n",
    "            return x == x[::-1]\n",
    "        \n",
    "        ans = 0\n",
    "\n",
    "        # odd\n",
    "        for k in range(MAGIC):\n",
    "            s = str(k)\n",
    "            t = s + s[-2::-1]\n",
    "            v = int(t) ** 2\n",
    "            if v > R: break\n",
    "            if v >= L and is_palindrome(str(v)): \n",
    "                ans += 1\n",
    "\n",
    "        # even\n",
    "        for k in range(MAGIC):\n",
    "            s = str(k)  # '1234'\n",
    "            t = s + s[::-1]  # '12344321' \n",
    "            v = int(t) ** 2\n",
    "            if v > R: break\n",
    "            if v >= L and is_palindrome(str(v)):\n",
    "                ans += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "L, R = 1, 10 ** 18\n",
    "limit = sqrt(R)\n",
    "res = []\n",
    "seed = 1\n",
    "num = 0\n",
    "def evenEnlarge(num):\n",
    "    tmp = num\n",
    "    while num:\n",
    "        tmp = tmp * 10 + num % 10\n",
    "        num //= 10\n",
    "    return tmp\n",
    "def oddEnlarge(num):\n",
    "    tmp = num\n",
    "    num //= 10\n",
    "    while num:\n",
    "        tmp = tmp * 10 + num % 10\n",
    "        num //= 10\n",
    "    return tmp\n",
    "def isPalindrome(num):\n",
    "    offset = 1\n",
    "    while num // offset >= 10:\n",
    "        offset *= 10\n",
    "    while num:\n",
    "        if num // offset != num % 10:\n",
    "            return False\n",
    "        num = (num % offset) // 10\n",
    "        offset //= 100\n",
    "    return True\n",
    "def check(num, l, r):\n",
    "    return l <= num <= r and isPalindrome(num)\n",
    "while num < limit:\n",
    "    num = evenEnlarge(seed)\n",
    "    if check(num * num, L, R):\n",
    "        res.append(num * num)\n",
    "    num = oddEnlarge(seed)\n",
    "    if check(num * num, L, R):\n",
    "        res.append(num * num)\n",
    "    seed += 1\n",
    "res.sort()\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        ans = 0\n",
    "        for x in res:\n",
    "            if int(left) <= x <= int(right):\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left, right) -> int:\n",
    "        left = int(left)\n",
    "        right = int(right)\n",
    "        def cal(pre, siz):\n",
    "            pre = str(pre)\n",
    "            if siz % 2:\n",
    "                return int(pre + pre[-2::-1])\n",
    "            else:\n",
    "                return int(pre + pre[::-1])\n",
    "        \n",
    "        def check(s):\n",
    "            s = str(s)\n",
    "            return s == s[::-1]\n",
    "        siz = 0\n",
    "        s = 1\n",
    "        t = 1\n",
    "        ans = 0\n",
    "        while True:\n",
    "            siz += 1\n",
    "            t *= 10\n",
    "            for i in range(s, t):\n",
    "                cur = cal(i, siz) ** 2\n",
    "                #print(cur, cal(i, siz), i)\n",
    "                if cur > right:\n",
    "                    return ans\n",
    "                elif cur >= left and check(cur):\n",
    "                    ans += 1\n",
    "            siz += 1\n",
    "            for i in range(s, t):\n",
    "                cur = cal(i, siz) ** 2\n",
    "                #print(cur)\n",
    "                if cur > right:\n",
    "                    return ans\n",
    "                elif cur >= left and check(cur):\n",
    "                    #print(cur)\n",
    "                    ans += 1\n",
    "            s *= 10\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        def is_circle(num):\n",
    "            s = str(num)\n",
    "            return s == s[::-1]\n",
    "\n",
    "        def create_circle(num):\n",
    "            s = str(num)\n",
    "            first = int(s + s[::-1])\n",
    "            second = int(s[:-1] + s[::-1])\n",
    "            return first, second\n",
    "\n",
    "        l = int(math.sqrt(int(left)))\n",
    "        r = int(math.sqrt(int(right))) + 1\n",
    "        # print(l, r)\n",
    "        ans = 0\n",
    "        for num in range(1, 100000):\n",
    "            # print(num)\n",
    "            big, small = create_circle(num)\n",
    "            # print(big, small)\n",
    "            if l <= small < r:\n",
    "                if is_circle(small * small):\n",
    "                    ans += 1\n",
    "            if l <= big < r:\n",
    "                if is_circle(big * big):\n",
    "                    ans += 1\n",
    "            if small > r:\n",
    "                break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        def check(x,l,r):\n",
    "            x=int(x)\n",
    "            l=int(l)\n",
    "            r=int(r)\n",
    "            x*=x\n",
    "            if x<l or x>r:\n",
    "                return False\n",
    "            x=str(x)\n",
    "            li,ri=0,len(x)-1\n",
    "            while li<ri:\n",
    "                if x[li]!=x[ri]:\n",
    "                    return False\n",
    "                li+=1\n",
    "                ri-=1\n",
    "            return True\n",
    "        res=0\n",
    "        for i in range(1,20002):\n",
    "            i=str(i)\n",
    "            j=i[::-1]\n",
    "            if check(i+j,left,right):\n",
    "                res+=1\n",
    "            if check(i+j[1:],left,right):\n",
    "                res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "\n",
    "\n",
    "        L, R = int(left), int(right)\n",
    "\n",
    "        MAGIC = 100000\n",
    "        res = 0\n",
    "\n",
    "        def isparlindrome(x):\n",
    "            def reverse(x):\n",
    "                res = 0\n",
    "                while x:\n",
    "                    res = res * 10 + x % 10\n",
    "                    x //= 10\n",
    "                return res\n",
    "            return x == reverse(x)\n",
    "\n",
    "        \n",
    "        for k in range(MAGIC):\n",
    "            s = str(k)\n",
    "            t = s + s[-2::-1]\n",
    "            v = int(t) ** 2\n",
    "            if v > R:break\n",
    "            if v >= L and isparlindrome(v):\n",
    "                res += 1\n",
    "        \n",
    "        for k in range(MAGIC):\n",
    "            s = str(k)\n",
    "            t = s + s[::-1]\n",
    "            v = int(t) ** 2\n",
    "            if v > R: break\n",
    "            if v >= L and isparlindrome(v):\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "def dfs(n,c):\n",
    "    if c == 0:\n",
    "        x = n ** 2\n",
    "        if str(x) == str(x)[::-1]:\n",
    "            res.append(x)\n",
    "        return\n",
    "    if c == i:\n",
    "        r = range(1,3)\n",
    "    else:\n",
    "        r = range(3)\n",
    "    for j in r:\n",
    "        dfs(n*10+j,c-1)\n",
    "\n",
    "res = []\n",
    "for i in range(1,10):\n",
    "    dfs(0,i)\n",
    "\n",
    "res.insert(2,9)\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        return bisect.bisect_right(res,int(right)) - bisect.bisect_left(res,int(left))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        l, r = int(left), int(right)\n",
    "        ans = 0\n",
    "        MAGIC = 100000\n",
    "\n",
    "        def reverse(k: int):\n",
    "            ans = 0\n",
    "            while k:\n",
    "                ans = ans * 10 + k % 10\n",
    "                k //= 10\n",
    "            return ans\n",
    "\n",
    "        def is_palin(k: int):\n",
    "            return k == reverse(k)\n",
    "\n",
    "        for i in range(1, MAGIC):\n",
    "            a = str(i)\n",
    "            a += a[::-1]\n",
    "            b = int(a) ** 2\n",
    "            if b > r:\n",
    "                break\n",
    "            if b >= l and is_palin(b):\n",
    "                ans += 1\n",
    "        \n",
    "        for i in range(1, MAGIC):\n",
    "            a = str(i)\n",
    "            a += a[-2::-1]\n",
    "            b = int(a) ** 2\n",
    "            if b > r:\n",
    "                break\n",
    "            if b >= l and is_palin(b):\n",
    "                ans += 1\n",
    "        \n",
    "        return ans\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        L,R = int(left),int(right)\n",
    "        MAGIC = 100000\n",
    "        def reverse(x):\n",
    "            ans = 0\n",
    "            while x:\n",
    "                ans = ans * 10 + x % 10\n",
    "                x //= 10\n",
    "            return ans\n",
    "        def eq(x):\n",
    "            return x == reverse(x)\n",
    "        ans = 0\n",
    "        for k in range(MAGIC):\n",
    "            s = str(k)\n",
    "            s = s + s[-2::-1]\n",
    "            v = int(s) ** 2\n",
    "            if v > R:\n",
    "                break\n",
    "            if v >= L and eq(v):\n",
    "                ans += 1\n",
    "        for k in range(MAGIC):\n",
    "            s = str(k)\n",
    "            s = s + s[::-1]\n",
    "            v = int(s) ** 2\n",
    "            if v > R:\n",
    "                break\n",
    "            if v >= L and eq(v):\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        MX = 10**5\n",
    "        left = int(left)\n",
    "        right = int(right)\n",
    "        def check(x):\n",
    "            x = str(x)\n",
    "            return x==x[::-1]\n",
    "        ans = 0\n",
    "        for k in range(MX):\n",
    "            k = str(k)\n",
    "            k = int(k+ k[-2::-1])\n",
    "            k2 = k**2\n",
    "            if k2>right:\n",
    "                break\n",
    "            if k2>=left and check(k2):\n",
    "                ans+=1\n",
    "        \n",
    "        for k in range(MX):\n",
    "            k = str(k)\n",
    "            k = int(k+ k[::-1])\n",
    "            k2 = k**2\n",
    "            if k2>right:\n",
    "                break\n",
    "            if k2>=left and check(k2):\n",
    "                ans+=1\n",
    "        \n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        #构造回文去是平方数是不是回文\n",
    "        cache = set()\n",
    "        def huiwen(s):\n",
    "            #if s in cache:\n",
    "            #    return True\n",
    "            l = 0\n",
    "            r = len(s)-1\n",
    "            while l<r:\n",
    "                if s[l] != s[r]:\n",
    "                    return False\n",
    "                l += 1\n",
    "                r -= 1\n",
    "            cache.add(s)\n",
    "            return True\n",
    "\n",
    "        ln = int(left)\n",
    "        rn = int(right)\n",
    "        res = 0\n",
    "        magic = 100000 #18/2/2\n",
    "        #构造回文数\n",
    "        #构造奇数位数回文数\n",
    "        for i in range(1,magic):\n",
    "            s = str(i)\n",
    "            t = s+s[-2::-1]\n",
    "            s2 = int(t)**2\n",
    "            if s2 > rn:\n",
    "                break\n",
    "            if s2 >= ln and huiwen(str(s2)):\n",
    "                res+=1\n",
    "        #构造偶数位回文数\n",
    "        for i in range(1,magic):\n",
    "            s = str(i)\n",
    "            t = s+s[::-1]\n",
    "            s2 = int(t)**2\n",
    "            if s2 > rn:\n",
    "                break\n",
    "            if s2 >= ln and huiwen(str(s2)):\n",
    "                res+=1\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "\n",
    "\n",
    "        L, R = int(left), int(right)\n",
    "\n",
    "        MAGIC = 100000\n",
    "        res = 0\n",
    "\n",
    "        def isparlindrome(x):\n",
    "            def reverse(x):\n",
    "                res = 0\n",
    "                while x:\n",
    "                    res = res * 10 + x % 10\n",
    "                    x //= 10\n",
    "                return res\n",
    "            return x == reverse(x)\n",
    "\n",
    "        \n",
    "        for k in range(MAGIC):\n",
    "            s = str(k)\n",
    "            t = s + s[-2::-1]\n",
    "            v = int(t) ** 2\n",
    "            if v > R:break\n",
    "            if v >= L and isparlindrome(v):\n",
    "                res += 1\n",
    "        \n",
    "        for k in range(MAGIC):\n",
    "            s = str(k)\n",
    "            t = s + s[::-1]\n",
    "            v = int(t) ** 2\n",
    "            if v > R: break\n",
    "            if v >= L and isparlindrome(v):\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 还是预处理就能解决问题的\n",
    "ans = set()\n",
    "for x in range(10**5):\n",
    "    if str(x) == str(x)[::-1] and str(x**2) == str(x**2)[::-1]:\n",
    "        ans.add(x**2)\n",
    "    y = int(str(x) + str(x)[::-1])\n",
    "    if str(y) == str(y)[::-1] and str(y**2) == str(y**2)[::-1]:\n",
    "        ans.add(y**2)\n",
    "    for i in range(10):\n",
    "        z = int(str(x) + str(i) + str(x)[::-1])\n",
    "        if str(z) == str(z)[::-1] and str(z**2) == str(z**2)[::-1]:\n",
    "            ans.add(z**2)\n",
    "ans = sorted(list(ans))\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        left = int(left)\n",
    "        right = int(right)\n",
    "        return bisect_right(ans, right) - bisect_left(ans, left)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def dfs(n, c):\n",
    "    if c == 0:\n",
    "        s = int(n) ** 2\n",
    "        if str(s) == str(s)[::-1]:\n",
    "            res.append(s)\n",
    "        return\n",
    "    if c == i:\n",
    "        r = range(1, 3)\n",
    "    else:\n",
    "        r = range(3)\n",
    "    for j in r:\n",
    "        dfs(n + str(j), c - 1)\n",
    "\n",
    "res = []\n",
    "for i in range(1, 10):\n",
    "    dfs(\"\", i)\n",
    "res.insert(2, 9)\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        return bisect.bisect_right(res, int(right)) - bisect.bisect_left(res, int(left))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "is_pa = lambda x: str(x) == str(x)[::-1]\n",
    "\n",
    "arr = []\n",
    "for num in range(10**6):\n",
    "    # odd\n",
    "    r_o, r_e = num // 10, num\n",
    "    val_o, val_e = num, num\n",
    "    while r_o:\n",
    "        r_o, r = divmod(r_o, 10)\n",
    "        val_o = val_o * 10 + r\n",
    "    if is_pa(val_o**2):\n",
    "        arr.append(val_o**2)\n",
    "    # even\n",
    "    if num < 10**5:\n",
    "        while r_e:\n",
    "            r_e, r = divmod(r_e, 10)\n",
    "            val_e = val_e * 10 + r\n",
    "        if is_pa(val_e**2):\n",
    "            arr.append(val_e**2)\n",
    "arr.sort()\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        l, r = int(left), int(right)\n",
    "        return bisect.bisect_left(arr, r + 1) - bisect.bisect_left(arr, l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        \"\"\"\n",
    "        R最大10^18，假设R=A^2，则A最大10^9，则A=B+B'，B表示A的一半，B'表示B的翻转\n",
    "        则B最大10^5，遍历B即可\n",
    "        \"\"\"\n",
    "        # 是否是回文数\n",
    "        def is_palindrome(n):\n",
    "            s = str(n)\n",
    "            mid = len(s) // 2\n",
    "            first_half = s[:mid]\n",
    "            second_half = first_half[::-1]\n",
    "            first_half_with_mid = s[:len(s)-mid]\n",
    "            s_revert = first_half_with_mid + second_half\n",
    "            return s == s_revert\n",
    "        \n",
    "        res, L, R = 0, int(left), int(right)\n",
    "        for B in range(10 ** 5):\n",
    "            s =str(B)\n",
    "            t1 = s + s[-2::-1] # 奇数位数，比如 s=1234，t=1234321\n",
    "            t2 = s + s[::-1] # 偶数位数，比如 s=1234，t=12344321\n",
    "\n",
    "            v1 = int(t1) ** 2\n",
    "            v2 = int(t2) ** 2\n",
    "\n",
    "            if v1 > R and v2 > R:\n",
    "                break\n",
    "            \n",
    "            if L <= v1 <= R and is_palindrome(v1):\n",
    "                res += 1\n",
    "            if L <= v2 <= R and is_palindrome(v2):\n",
    "                res += 1\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        l = ceil(sqrt(int(left)))\n",
    "        r = floor(sqrt(int(right)))\n",
    "\n",
    "        ans = 0\n",
    "        def helper(i) :\n",
    "            nonlocal ans\n",
    "            if int(i) > r or len(i) > len(str(r)):\n",
    "                return 0\n",
    "            if int(i) >= l and i[0] != '0':\n",
    "                if dfs(str(int(i) * int(i))) :\n",
    "                    ans += 1\n",
    "            for j in range(10) :\n",
    "                helper(str(j) + i + str(j))\n",
    "\n",
    "        def helper2(i) :\n",
    "            nonlocal ans\n",
    "            if int(i) > r or len(i) > len(str(r)):\n",
    "                return 0\n",
    "            if int(i) >= l and i[0] != '0':\n",
    "                if dfs(str(int(i) * int(i))) :\n",
    "                    ans += 1\n",
    "            for j in range(10) :\n",
    "                helper2(str(j) + i + str(j))\n",
    "        \n",
    "        def dfs(s) :\n",
    "            if len(s) == 1 :\n",
    "                return True\n",
    "            l, r = 0, len(s)-1\n",
    "            while l < r :\n",
    "                if s[l] != s[r] :\n",
    "                    return False\n",
    "                l += 1 \n",
    "                r -= 1\n",
    "            return True\n",
    "            \n",
    "        for i in range(10) :\n",
    "            helper(str(i))\n",
    "            helper2(str(i)+str(i))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        L, R = int(left), int(right)\n",
    "        MAGIC = 100000  # A magic number that limits the search space\n",
    "        ans = 0\n",
    "\n",
    "        # First, let's create palindrome by the half and the odd-even method\n",
    "        def is_palindrome(n):\n",
    "            return str(n) == str(n)[::-1]\n",
    "\n",
    "        # Even length palindromes\n",
    "        for k in range(MAGIC):\n",
    "            s = str(k)\n",
    "            t = s + s[::-1]\n",
    "            v = int(t) ** 2\n",
    "            if v > R:\n",
    "                break\n",
    "            if v >= L and is_palindrome(v):\n",
    "                ans += 1\n",
    "        \n",
    "        # Odd length palindromes\n",
    "        for k in range(MAGIC):\n",
    "            s = str(k)\n",
    "            t = s + s[-2::-1]  # Exclude the last character for the second half\n",
    "            v = int(t) ** 2\n",
    "            if v > R:\n",
    "                break\n",
    "            if v >= L and is_palindrome(v):\n",
    "                ans += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        count = 0\n",
    "        L = int(left)\n",
    "        R = int(right)\n",
    "\n",
    "        def check(num):\n",
    "            if 0 <= num < 10:\n",
    "                return True\n",
    "            numm = num\n",
    "            res = 0\n",
    "            while num != 0:\n",
    "                res, num = 10 * res + num % 10, num // 10\n",
    "            return res == numm\n",
    "        \n",
    "        # ranging from 1 to 10\n",
    "        for i in range(1, 10):\n",
    "            if L <= i ** 2 <= R and check(i ** 2):\n",
    "                count += 1\n",
    "\n",
    "        # ranging from 10 to 10000 \n",
    "        for ii in range(10000):\n",
    "            # even\n",
    "            i = str(ii)\n",
    "            tar_even = int(i + i[::-1])\n",
    "            tar_even **= 2\n",
    "            if L <= tar_even <= R and check(tar_even):\n",
    "                count += 1\n",
    "            # odd\n",
    "            for j in range(10):\n",
    "                tar_odd = int(i + str(j) + i[::-1])\n",
    "                tar_odd **= 2\n",
    "                if L <= tar_odd <= R and check(tar_odd):\n",
    "                    count += 1  \n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        L, R = int(left), int(right)\n",
    "        MAGIC = 100000\n",
    "\n",
    "        def reverse(x):\n",
    "            ans = 0\n",
    "            while x:\n",
    "                ans = 10 * ans + x % 10\n",
    "                x //= 10\n",
    "            return ans\n",
    "\n",
    "        def is_palindrome(x):\n",
    "            return x == reverse(x)\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        # count odd length\n",
    "        for k in range(MAGIC):\n",
    "            s = str(k)  # Eg. s = '1234'\n",
    "            t = s + s[-2::-1]  # t = '1234321'\n",
    "            v = int(t) ** 2\n",
    "            if v > R: \n",
    "                break\n",
    "            if v >= L and is_palindrome(v):\n",
    "                ans += 1\n",
    "\n",
    "        # count even length\n",
    "        for k in range(MAGIC):\n",
    "            s = str(k)  # Eg. s = '1234'\n",
    "            t = s + s[::-1]  # t = '12344321'\n",
    "            v = int(t) ** 2\n",
    "            if v > R: \n",
    "                break\n",
    "            if v >= L and is_palindrome(v):\n",
    "                ans += 1\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        left, right = int(left), int(right)\n",
    "    \n",
    "        def is_palindrome(s):\n",
    "            return s == s[::-1]\n",
    "        \n",
    "        count = 0\n",
    "\n",
    "        for i in range(1, 10**5):\n",
    "            s = str(i)\n",
    "            palindrome = int(s + s[-2::-1])**2  # 构造回文数的平方\n",
    "            if palindrome > right:\n",
    "                break\n",
    "            if palindrome >= left and is_palindrome(str(palindrome)):\n",
    "                count += 1\n",
    "        \n",
    "\n",
    "        for i in range(1, 10**5):\n",
    "            s = str(i)\n",
    "            palindrome = int(s + s[::-1])**2\n",
    "            if palindrome > right:\n",
    "                break\n",
    "            if palindrome >= left and is_palindrome(str(palindrome)):\n",
    "                count += 1\n",
    "        \n",
    "        return count\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "\n",
    "\n",
    "        L, R = int(left), int(right)\n",
    "\n",
    "        MAGIC = 100000\n",
    "        res = 0\n",
    "\n",
    "        def isparlindrome(x):\n",
    "            def reverse(x):\n",
    "                res = 0\n",
    "                while x:\n",
    "                    res = res * 10 + x % 10\n",
    "                    x //= 10\n",
    "                return res\n",
    "            return x == reverse(x)\n",
    "\n",
    "        \n",
    "        for k in range(MAGIC):\n",
    "            s = str(k)\n",
    "            t = s + s[-2::-1]\n",
    "            v = int(t) ** 2\n",
    "            if v > R:break\n",
    "            if v >= L and isparlindrome(v):\n",
    "                res += 1\n",
    "        \n",
    "        for k in range(MAGIC):\n",
    "            s = str(k)\n",
    "            t = s + s[::-1]\n",
    "            v = int(t) ** 2\n",
    "            if v > R: break\n",
    "            if v >= L and isparlindrome(v):\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        def is_palindrame(x):\n",
    "            return str(x) == str(x)[::-1]\n",
    "        \n",
    "        left = int(left)\n",
    "        right = int(right)\n",
    "\n",
    "        max_num = 100000\n",
    "        cnt = 0\n",
    "\n",
    "        for i in range(max_num):\n",
    "            n = str(i) + str(i)[-2::-1]\n",
    "            k = int(n) ** 2\n",
    "\n",
    "            if k > right:\n",
    "                break\n",
    "            if k >= left and is_palindrame(k):\n",
    "                cnt += 1\n",
    "\n",
    "        for i in range(max_num):\n",
    "            n = str(i) + str(i)[-1::-1]\n",
    "            k = int(n) ** 2\n",
    "\n",
    "            if k > right:\n",
    "                break\n",
    "            if k >= left and is_palindrame(k):\n",
    "                cnt += 1\n",
    "        \n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        l = int(left)\n",
    "        r = int(right)\n",
    "        threshhold = 100000\n",
    "\n",
    "        def reverse(x):\n",
    "            ans = 0\n",
    "            while x:\n",
    "                ans = ans * 10 + x % 10\n",
    "                x //= 10\n",
    "\n",
    "            return ans\n",
    "\n",
    "        def isPalindrome(x):\n",
    "            return x == reverse(x)\n",
    "\n",
    "\n",
    "        ans = 0\n",
    "        # count odd length\n",
    "        for k in range(threshhold):\n",
    "            s = str(k) # eg, s='1234'\n",
    "            t = s + s[-2::-1] # t = 1234321\n",
    "            v = int(t) ** 2\n",
    "            if v > r:\n",
    "                break\n",
    "            if v >= l and isPalindrome(v):\n",
    "                ans += 1\n",
    "\n",
    "        # count even length\n",
    "        for k in range(threshhold):\n",
    "            s = str(k)\n",
    "            t = s + s[::-1]\n",
    "            v = int(t) ** 2\n",
    "            if v > r:\n",
    "                break\n",
    "            if v >= l and isPalindrome(v):\n",
    "                ans += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        cache = set()\n",
    "        def huiwen(s):\n",
    "            #if s in cache:\n",
    "            #    return True\n",
    "            l = 0\n",
    "            r = len(s)-1\n",
    "            while l<r:\n",
    "                if s[l] != s[r]:\n",
    "                    return False\n",
    "                l += 1\n",
    "                r -= 1\n",
    "            cache.add(s)\n",
    "            return True\n",
    "\n",
    "        ln = int(left)\n",
    "        rn = int(right)\n",
    "        res = 0\n",
    "        magic = 100000 #18/2/2\n",
    "        #构造回文数\n",
    "        #构造奇数位数回文数\n",
    "        for i in range(1,magic):\n",
    "            s = str(i)\n",
    "            t = s+s[-2::-1]\n",
    "            s2 = int(t)**2\n",
    "            if s2 > rn:\n",
    "                break\n",
    "            if s2 >= ln and huiwen(str(s2)):\n",
    "                res+=1\n",
    "        #构造偶数位回文数\n",
    "        for i in range(1,magic):\n",
    "            s = str(i)\n",
    "            t = s+s[::-1]\n",
    "            s2 = int(t)**2\n",
    "            if s2 > rn:\n",
    "                break\n",
    "            if s2 >= ln and huiwen(str(s2)):\n",
    "                res+=1\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        def nextMirror(n: str) -> str:\n",
    "            s = list(n)\n",
    "            d = len(s)\n",
    "            if s == ['9']*d:\n",
    "                return '1' +'0'*(d-1) + '1'\n",
    "            if d % 2:\n",
    "                if s[d // 2] != '9':\n",
    "                    s[d // 2] = str(int(s[d // 2]) + 1)\n",
    "                    return ''.join(s)\n",
    "                else:\n",
    "                    s[d // 2] = '0'\n",
    "            change = d // 2 - 1\n",
    "            while s[change] == '9':\n",
    "                s[change], s[d-1-change] = '0', '0'\n",
    "                change -= 1\n",
    "            s[change] = str(int(s[change]) + 1)\n",
    "            s[d-1-change] = str(int(s[d-1-change]) + 1)\n",
    "            return ''.join(s)\n",
    "        \n",
    "        def isP(n: str):\n",
    "            ln = len(n)\n",
    "            for i in range(ln//2):\n",
    "                if n[i] != n[ln-1-i]:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        now = \"1\"\n",
    "        nowres = int(now)**2\n",
    "        res = 0\n",
    "        while nowres <= int(right):\n",
    "            if isP(str(nowres)) and nowres >= int(left):\n",
    "                res += 1\n",
    "            now = nextMirror(now)\n",
    "            nowres = int(now)**2\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 简要说明： 超级回文数的首位必定为1或4,它的开平方首（尾）位必定为1,2，第二位不超过3.\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        L=ceil(pow(int(left),0.5))\n",
    "        R=floor(pow(int(right),0.5))\n",
    "        rs=0\n",
    "\n",
    "        if L<101:\n",
    "            for n in range(L,min(R+1,23)):\n",
    "                if n in (0,1,2,3,11,22):\n",
    "                    rs+=1\n",
    "        if R<=100: return rs            \n",
    "\n",
    "\n",
    "        n=max(101,L)\n",
    "        # 确定进入循环的回文数\n",
    "        sn = str(n)\n",
    "        l=len(sn)\n",
    "        ppp=(l+1)//2\n",
    "        la=l%2     \n",
    "        pre_sn=sn[0:ppp]   # 如果 la=1,说明pre_sn的最后一位是共有位，否则为对称位。\n",
    "        if int(pre_sn[0])>2 or ((pre_sn[0])=='2' and int(pre_sn[1])>2):\n",
    "            n=(10**l)+1\n",
    "            l+=1\n",
    "            ppp=(l+1)//2\n",
    "            la=1-la\n",
    "        elif int(pre_sn[0])==1  and int(pre_sn[1])>2:\n",
    "            n=2*(10**(l-1))+2\n",
    "        elif la:\n",
    "            sn=pre_sn+pre_sn[0:ppp-1][::-1]\n",
    "            if int(sn)>=n:\n",
    "                n=int(sn)\n",
    "            else:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp-1][::-1])\n",
    "        else:\n",
    "            sn=pre_sn+pre_sn[0:ppp][::-1]\n",
    "            if int(sn)>=n:\n",
    "                n=int(sn)\n",
    "            else:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp][::-1])\n",
    "\n",
    "        #此时n为回文数\n",
    "\n",
    "        while n <= R :\n",
    "            \n",
    "            if (ss:=str(n*n))==ss[::-1]: rs+=1\n",
    "\n",
    "            #产生下一个回文数\n",
    "            sn = str(n)\n",
    "            pre_sn=sn[0:ppp]\n",
    "            if int(pre_sn[0])>2 or ((pre_sn[0])=='2' and int(pre_sn[1])>1): #首位小于3 并且 首两位小于23\n",
    "                n=(10**l)+1\n",
    "                l+=1\n",
    "                ppp=(l+1)//2\n",
    "                la=1-la\n",
    "            elif int(pre_sn[0])==1  and int(pre_sn[1])>1:      #11,12 打头符合，13不符合\n",
    "                n=2*(10**(l-1))+2\n",
    "            elif la:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp-1][::-1])\n",
    "            else:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp][::-1])\n",
    "        return rs       \n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "\n",
    "        left, right = int(left), int(right)\n",
    "\n",
    "        def reverse(x):\n",
    "            cur = 0\n",
    "            while x:\n",
    "                cur = cur * 10 + x % 10\n",
    "                x //= 10\n",
    "            return cur\n",
    "        ans = 0\n",
    "        for i in range(10 ** 5):\n",
    "            t = str(i)\n",
    "            post = t[-2::-1]\n",
    "            cur = t + post\n",
    "            if int(cur) ** 2 > right:\n",
    "                break\n",
    "            else:\n",
    "                if int(cur) ** 2 >= left:\n",
    "                    if reverse(int(cur) ** 2) == int(cur) ** 2:\n",
    "                        ans += 1\n",
    "        for i in range(10 ** 5):\n",
    "            t = str(i)\n",
    "            post = t[::-1]\n",
    "            cur = t + post\n",
    "            if int(cur) ** 2 > right:\n",
    "                break\n",
    "            else:\n",
    "                if int(cur) ** 2 >= left:\n",
    "                    if reverse(int(cur) ** 2) == int(cur) ** 2:\n",
    "                        ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        left = int(left)\n",
    "        right = int(right)\n",
    "        def is_palindromic(num):\n",
    "            num = str(num)\n",
    "            n = len(num)\n",
    "            half = n // 2\n",
    "            if n%2 == 0:\n",
    "                ans = num[:half] == num[-1:half-1:-1]\n",
    "            elif n%2 == 1:\n",
    "                ans = num[:half] == num[-1:half:-1]\n",
    "            return ans\n",
    "        \n",
    "        #odd\n",
    "        #x2 = y \n",
    "        l1 = int(left **0.5) -1\n",
    "        r1 = int(right**0.5) +1\n",
    "        ans = 0 \n",
    "        for i in range(1,10**5):\n",
    "            m1 = str(i)\n",
    "            m = int(m1+ m1[::-1])\n",
    "            n = m**2\n",
    "            if left <= n <= right and is_palindromic(n): \n",
    "                ans +=1\n",
    "\n",
    "        for i in range(1,10**5):\n",
    "            m1 = str(i)\n",
    "            m = int(m1+m1[-2::-1])\n",
    "            n = m**2\n",
    "            if left <= n <= right and is_palindromic(n):\n",
    "                ans += 1\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "\n",
    "        left, right = int(left), int(right)\n",
    "\n",
    "        def reverse(x):\n",
    "            cur = 0\n",
    "            while x:\n",
    "                cur = cur * 10 + x % 10\n",
    "                x //= 10\n",
    "            return cur\n",
    "        ans = 0\n",
    "        for i in range(10 ** 5):\n",
    "            t = str(i)\n",
    "            post = t[-2::-1]\n",
    "            cur = t + post\n",
    "            if int(cur) ** 2 > right:\n",
    "                break\n",
    "            else:\n",
    "                if int(cur) ** 2 >= left:\n",
    "                    if reverse(int(cur) ** 2) == int(cur) ** 2:\n",
    "                        ans += 1\n",
    "            t = str(i)\n",
    "            post = t[::-1]\n",
    "            cur = t + post\n",
    "            if int(cur) ** 2 <= right:\n",
    "                if int(cur) ** 2 >= left:\n",
    "                    if reverse(int(cur) ** 2) == int(cur) ** 2:\n",
    "                        ans += 1\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def check(s):\n",
    "    i = 0\n",
    "    j = len(s) - 1\n",
    "\n",
    "    while i <= j:\n",
    "        if s[i] != s[j]:\n",
    "            return False\n",
    "\n",
    "        i += 1\n",
    "        j -= 1\n",
    "\n",
    "    return True\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        sleft = left\n",
    "        left = int(left)\n",
    "        right = int(right)\n",
    "\n",
    "        ret = 0\n",
    "\n",
    "        # i = 10 ** (len(str(int(int(sleft[:max(len(sleft) // 2, 1)]) ** 0.5))) - 1)\n",
    "        i = 1\n",
    "        \n",
    "        while True:\n",
    "            for j in range(2):\n",
    "                for k in range(i, i * 10):\n",
    "                    s = str(k)\n",
    "                    s = s + s[:-1][::-1] if j == 0 else s + s[::-1]\n",
    "                    x = int(s)\n",
    "                    x2 = x ** 2\n",
    "\n",
    "                    if left <= x2 <= right and check(str(x2)):\n",
    "                        ret += 1\n",
    "\n",
    "                    elif x2 > right:\n",
    "                        return ret\n",
    "\n",
    "            i *= 10\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        L=ceil(pow(int(left),0.5))\n",
    "        R=floor(pow(int(right),0.5))\n",
    "        rs=0\n",
    "\n",
    "        if L<23:\n",
    "            for n in range(L,min(R+1,23)):\n",
    "                if n in (0,1,2,3,11,22):\n",
    "                    rs+=1\n",
    "\n",
    "        n=max(101,L)\n",
    "\n",
    "        # 确定首个回文数\n",
    "        sn = str(n)\n",
    "        l=len(sn)\n",
    "        ppp=(l+1)//2\n",
    "        la=l%2     \n",
    "        pre_sn=sn[0:ppp]   # 如果 la=1,说明pre_sn的最后一位是共有位，否则为对称位。\n",
    "        if int(pre_sn[0])>2 or ((pre_sn[0])=='2' and int(pre_sn[1])>2):\n",
    "            n=(10**l)+1\n",
    "            l+=1\n",
    "            ppp=(l+1)//2\n",
    "            la=1-la\n",
    "        elif int(pre_sn[0])==1  and int(pre_sn[1])>2:\n",
    "            n=2*(10**(l-1))+2\n",
    "        elif la:\n",
    "            sn=pre_sn+pre_sn[0:ppp-1][::-1]\n",
    "            if int(sn)>=n:\n",
    "                n=int(sn)\n",
    "            else:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp-1][::-1])\n",
    "        else:\n",
    "            sn=pre_sn+pre_sn[0:ppp][::-1]\n",
    "            if int(sn)>=n:\n",
    "                n=int(sn)\n",
    "            else:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp][::-1])\n",
    "\n",
    "\n",
    "\n",
    "        while n <= R :\n",
    "            \n",
    "            if (ss:=str(n*n))==ss[::-1]: rs+=1\n",
    "\n",
    "            #寻找下一个n\n",
    "            sn = str(n)\n",
    "            pre_sn=sn[0:ppp]\n",
    "\n",
    "            if int(pre_sn[0])>2 or ((pre_sn[0])=='2' and int(pre_sn[1])>2):\n",
    "                n=(10**l)+1\n",
    "                l+=1\n",
    "                ppp=(l+1)//2\n",
    "                la=1-la\n",
    "            elif int(pre_sn[0])==1  and int(pre_sn[1])>1:\n",
    "                n=2*(10**(l-1))+2\n",
    "            elif la:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp-1][::-1])\n",
    "            else:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp][::-1])\n",
    "        return rs       \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "               \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        L=ceil(pow(int(left),0.5))\n",
    "        R=floor(pow(int(right),0.5))\n",
    "        rs=0\n",
    "\n",
    "        if L<23:\n",
    "            for n in range(L,min(R+1,23)):\n",
    "                if n in (0,1,2,3,11,22):\n",
    "                    rs+=1\n",
    "\n",
    "        n=max(100,L)\n",
    "\n",
    "        # 确定首个回文数\n",
    "        sn = str(n)\n",
    "        l=len(sn)\n",
    "        ppp=(l+1)//2\n",
    "        la=l%2     \n",
    "        pre_sn=sn[0:ppp]   # 如果 la=1,说明pre_sn的最后一位是共有位，否则为对称位。\n",
    "        \n",
    "        if int(pre_sn[0])>2 or ((pre_sn[0])=='2' and int(pre_sn[1])>2):\n",
    "            n=(10**l)+1\n",
    "            l+=1\n",
    "            ppp=(l+1)//2\n",
    "            la=1-la\n",
    "        elif int(pre_sn[0])==1  and int(pre_sn[1])>2:\n",
    "            n=2*(10**(l-1))+2\n",
    "        elif la:\n",
    "            sn=pre_sn+pre_sn[0:ppp-1][::-1]\n",
    "            if int(sn)>=n:\n",
    "                n=int(sn)\n",
    "            else:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp-1][::-1])\n",
    "        else:\n",
    "            sn=pre_sn+pre_sn[0:ppp][::-1]\n",
    "            if int(sn)>=n:\n",
    "                n=int(sn)\n",
    "            else:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp][::-1])\n",
    "\n",
    "\n",
    "\n",
    "        while n <= R :\n",
    "            \n",
    "            if (ss:=str(n*n))==ss[::-1]: rs+=1\n",
    "\n",
    "            #寻找下一个n\n",
    "            sn = str(n)\n",
    "\n",
    "            pre_sn=sn[0:ppp]\n",
    "\n",
    "\n",
    "            if int(pre_sn[0])>2 or ((pre_sn[0])=='2' and int(pre_sn[1])>2):\n",
    "                n=(10**l)+1\n",
    "                l+=1\n",
    "                ppp=(l+1)//2\n",
    "                la=1-la\n",
    "            elif int(pre_sn[0])==1  and int(pre_sn[1])>1:\n",
    "                n=2*(10**(l-1))+2\n",
    "            elif la:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp-1][::-1])\n",
    "            else:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp][::-1])\n",
    "        return rs       \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "               \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def superpalindromesInRange(self, L, R):\n",
    "        L, R = int(L), int(R)\n",
    "        MAGIC = 100000\n",
    "\n",
    "        def reverse(x):\n",
    "            ans = 0\n",
    "            while x:\n",
    "                ans = 10 * ans + x % 10\n",
    "                x //= 10\n",
    "            return ans\n",
    "\n",
    "        def is_palindrome(x):\n",
    "            return x == reverse(x)\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        # count odd length\n",
    "        for k in range(MAGIC):\n",
    "            s = str(k)  # Eg. s = '1234'\n",
    "            t = s + s[-2::-1]  # t = '1234321'\n",
    "            v = int(t) ** 2\n",
    "            if v > R: break\n",
    "            if v >= L and is_palindrome(v):\n",
    "                ans += 1\n",
    "\n",
    "        # count even length\n",
    "        for k in range(MAGIC):\n",
    "            s = str(k)  # Eg. s = '1234'\n",
    "            t = s + s[::-1]  # t = '12344321'\n",
    "            v = int(t) ** 2\n",
    "            if v > R: break\n",
    "            if v >= L and is_palindrome(v):\n",
    "                ans += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        L, R = int(left), int(right)\n",
    "        MAGIC = 100000\n",
    "\n",
    "        def reverse(x):\n",
    "            \n",
    "            return x[::-1]\n",
    "        \n",
    "        def is_palindrome(x):\n",
    "            return x == reverse(x)\n",
    "        \n",
    "        ans = 0\n",
    "\n",
    "        # odd\n",
    "        for k in range(MAGIC):\n",
    "            s = str(k)\n",
    "            t = s + s[-2::-1]\n",
    "            v = int(t) ** 2\n",
    "            if v > R: break\n",
    "            if v >= L and is_palindrome(str(v)): \n",
    "                ans += 1\n",
    "\n",
    "        # even\n",
    "        for k in range(MAGIC):\n",
    "            s = str(k)  # '1234'\n",
    "            t = s + s[::-1]  # '12344321' \n",
    "            v = int(t) ** 2\n",
    "            if v > R: break\n",
    "            if v >= L and is_palindrome(str(v)):\n",
    "                ans += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        res = [1, 4, 9, 121, 484, 10201, 12321, 14641, 40804, 44944, 1002001, 1234321, 4008004, 100020001, 102030201, 104060401, 121242121, 123454321, 125686521, 400080004, 404090404, 10000200001, 10221412201, 12102420121, 12345654321, 40000800004, 1000002000001, 1002003002001, 1004006004001, 1020304030201, 1022325232201, 1024348434201, 1210024200121, 1212225222121, 1214428244121, 1232346432321, 1234567654321, 4000008000004, 4004009004004, 100000020000001, 100220141022001, 102012040210201, 102234363432201, 121000242000121, 121242363242121, 123212464212321, 123456787654321, 400000080000004, 10000000200000001, 10002000300020001, 10004000600040001, 10020210401202001, 10022212521222001, 10024214841242001, 10201020402010201, 10203040504030201, 10205060806050201, 10221432623412201, 10223454745432201, 12100002420000121, 12102202520220121, 12104402820440121, 12122232623222121, 12124434743442121, 12321024642012321, 12323244744232321, 12343456865434321, 12345678987654321, 40000000800000004, 40004000900040004]\n",
    "        ans = 0\n",
    "        for x in res:\n",
    "            if int(left) <= x <= int(right):\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def check(s):\n",
    "    i = 0\n",
    "    j = len(s) - 1\n",
    "\n",
    "    while i <= j:\n",
    "        if s[i] != s[j]:\n",
    "            return False\n",
    "\n",
    "        i += 1\n",
    "        j -= 1\n",
    "\n",
    "    return True\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        sleft = left\n",
    "        left = int(left)\n",
    "        right = int(right)\n",
    "\n",
    "        ret = 0\n",
    "\n",
    "        i = 10 ** (len(str(int(int(sleft[:max(len(sleft) // 2, 1)]) ** 0.5))) - 1)\n",
    "\n",
    "        while True:\n",
    "            for j in range(2):\n",
    "                for k in range(i, i * 10):\n",
    "                    s = str(k)\n",
    "                    s = s + s[:-1][::-1] if j == 0 else s + s[::-1]\n",
    "                    x = int(s)\n",
    "                    x2 = x ** 2\n",
    "\n",
    "                    if left <= x2 <= right and check(str(x2)):\n",
    "                        ret += 1\n",
    "\n",
    "                    elif x2 > right:\n",
    "                        return ret\n",
    "\n",
    "            i *= 10\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        def check(num):\n",
    "            num = int(int(num) ** 2)\n",
    "            if num > num1:\n",
    "                return 2\n",
    "            if num < num0:\n",
    "                return 1\n",
    "            num = str(num)\n",
    "            i = 0\n",
    "            j = len(num) - 1\n",
    "            while i < j:\n",
    "                if num[i] != num[j]:\n",
    "                    return 1\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            \n",
    "            return 0\n",
    "        num0 = int(left)\n",
    "        num1 = int(right)\n",
    "\n",
    "        sqrt0 = int(num0**0.5)\n",
    "        if int(sqrt0) != sqrt0:\n",
    "            sqrt0 += 1\n",
    "        sqrt1 = int(num1**0.5)\n",
    "        length0 = 0\n",
    "        t = sqrt0\n",
    "        while t:\n",
    "            length0 += 1\n",
    "            t //= 10\n",
    "        length1 = 0\n",
    "        t = sqrt1\n",
    "        while t:\n",
    "            length1 += 1\n",
    "            t //= 10\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(int(10**(length0//2-1)), min(int(10**(length1//2+1)), 20002)):\n",
    "            s = str(i)\n",
    "            t0 = s + s[::-1]\n",
    "            if check(t0) == 0:\n",
    "                ans += 1\n",
    "            t1 = s + s[:-1][::-1]\n",
    "            tmp = check(t1)\n",
    "            if tmp == 0:\n",
    "                ans += 1\n",
    "            elif tmp == 2:\n",
    "                break\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        def check(num):\n",
    "            num = int(int(num) ** 2)\n",
    "            if num > num1:\n",
    "                return 2\n",
    "            if num < num0:\n",
    "                return 1\n",
    "            num = str(num)\n",
    "            i = 0\n",
    "            j = len(num) - 1\n",
    "            while i < j:\n",
    "                if num[i] != num[j]:\n",
    "                    return 1\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            \n",
    "            return 0\n",
    "        num0 = int(left)\n",
    "        num1 = int(right)\n",
    "\n",
    "        sqrt0 = int(num0**0.5)\n",
    "        if int(sqrt0) != sqrt0:\n",
    "            sqrt0 += 1\n",
    "        sqrt1 = int(num1**0.5)\n",
    "        length0 = 0\n",
    "        t = sqrt0\n",
    "        while t:\n",
    "            length0 += 1\n",
    "            t //= 10\n",
    "        length1 = 0\n",
    "        t = sqrt1\n",
    "        while t:\n",
    "            length1 += 1\n",
    "            t //= 10\n",
    "\n",
    "        ans = 0\n",
    "        flag = True\n",
    "        for i in range(int(10**(length0//2-1)), int(10**(length1//2+1))):\n",
    "            s = str(i)\n",
    "            if flag:\n",
    "                t0 = s + s[::-1]\n",
    "                tmp = check(t0)\n",
    "                if tmp == 0:\n",
    "                    ans += 1\n",
    "                elif tmp == 2:\n",
    "                    flag = False\n",
    "            t1 = s + s[:-1][::-1]\n",
    "            tmp = check(t1)\n",
    "            if tmp == 0:\n",
    "                ans += 1\n",
    "            elif tmp == 2:\n",
    "                break\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        L=ceil(pow(int(left),0.5))\n",
    "        R=floor(pow(int(right),0.5))\n",
    "        rs=0\n",
    "\n",
    "        if L<23:\n",
    "            for n in range(L,min(R+1,23)):\n",
    "                if n in (0,1,2,3,11,22):\n",
    "                    rs+=1\n",
    "\n",
    "        n=max(101,L)\n",
    "\n",
    "        # 确定首个回文数\n",
    "        sn = str(n)\n",
    "        l=len(sn)\n",
    "        ppp=(l+1)//2\n",
    "        la=l%2     \n",
    "        pre_sn=sn[0:ppp]   # 如果 la=1,说明pre_sn的最后一位是共有位，否则为对称位。\n",
    "        if int(pre_sn[0])>2 or ((pre_sn[0])=='2' and int(pre_sn[1])>2):\n",
    "            n=(10**l)+1\n",
    "            l+=1\n",
    "            ppp=(l+1)//2\n",
    "            la=1-la\n",
    "        elif int(pre_sn[0])==1  and int(pre_sn[1])>2:\n",
    "            n=2*(10**(l-1))+2\n",
    "        elif la:\n",
    "            sn=pre_sn+pre_sn[0:ppp-1][::-1]\n",
    "            if int(sn)>=n:\n",
    "                n=int(sn)\n",
    "            else:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp-1][::-1])\n",
    "        else:\n",
    "            sn=pre_sn+pre_sn[0:ppp][::-1]\n",
    "            if int(sn)>=n:\n",
    "                n=int(sn)\n",
    "            else:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp][::-1])\n",
    "\n",
    "\n",
    "\n",
    "        while n <= R :\n",
    "            \n",
    "            if (ss:=str(n*n))==ss[::-1]: rs+=1\n",
    "\n",
    "            #寻找下一个n\n",
    "            sn = str(n)\n",
    "            pre_sn=sn[0:ppp]\n",
    "            if int(pre_sn[0])>2 or ((pre_sn[0])=='2' and int(pre_sn[1])>2):\n",
    "                n=(10**l)+1\n",
    "                l+=1\n",
    "                ppp=(l+1)//2\n",
    "                la=1-la\n",
    "            elif int(pre_sn[0])==1  and int(pre_sn[1])>1:\n",
    "                n=2*(10**(l-1))+2\n",
    "            elif la:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp-1][::-1])\n",
    "            else:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp][::-1])\n",
    "        return rs       \n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        l_sqrt = int(math.ceil(math.sqrt(int(left))))\n",
    "        r_sqrt = int(math.floor(math.sqrt(int(right))))\n",
    "\n",
    "        l_len = len(str(l_sqrt))\n",
    "        r_len = len(str(r_sqrt))\n",
    "\n",
    "        cut = 0\n",
    "\n",
    "        for l in range(l_len, r_len + 1):\n",
    "            half_l = l // 2\n",
    "            if l % 2 == 0:\n",
    "                for st in range(10 ** (half_l - 1), 10 ** half_l):\n",
    "                    hw_st = int(str(st) + str(st)[::-1])\n",
    "                    if l_sqrt <= hw_st <= r_sqrt and str(hw_st ** 2) == str(hw_st ** 2)[::-1]:\n",
    "                        cut += 1\n",
    "            else:\n",
    "                if l == 1:\n",
    "                    for st in range(1, 10):\n",
    "                        st = int(st)\n",
    "                        if l_sqrt <= st <= r_sqrt and str(st ** 2) == str(st ** 2)[::-1]:\n",
    "                            cut += 1\n",
    "                else:\n",
    "                    num = ['0', '1', '2','3', '4', '5', '6', '7', '8', '9']\n",
    "                    for st in range(10 ** (half_l - 1), 10 ** half_l):\n",
    "                        for m in num:\n",
    "                            hw_st = int(str(st) + m + str(st)[::-1])\n",
    "                            if l_sqrt <= hw_st <= r_sqrt and str(hw_st ** 2) == str(hw_st ** 2)[::-1]:\n",
    "                                cut += 1\n",
    "        return cut"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        L=ceil(pow(int(left),0.5))\n",
    "        R=floor(pow(int(right),0.5))\n",
    "        rs=0\n",
    "\n",
    "        if L<23:\n",
    "\n",
    "            for n in range(L,min(R+1,23)):\n",
    "                if n in (0,1,2,3,11,22):\n",
    "                    rs+=1\n",
    "\n",
    "        if R<=100: return rs            \n",
    "\n",
    "        \n",
    "        n=max(101,L)\n",
    "\n",
    "\n",
    "        # 确定首个回文数\n",
    "        sn = str(n)\n",
    "        l=len(sn)\n",
    "        ppp=(l+1)//2\n",
    "        la=l%2     \n",
    "        pre_sn=sn[0:ppp]   # 如果 la=1,说明pre_sn的最后一位是共有位，否则为对称位。\n",
    "        if int(pre_sn[0])>2 or ((pre_sn[0])=='2' and int(pre_sn[1])>2):\n",
    "            n=(10**l)+1\n",
    "            l+=1\n",
    "            ppp=(l+1)//2\n",
    "            la=1-la\n",
    "        elif int(pre_sn[0])==1  and int(pre_sn[1])>2:\n",
    "            n=2*(10**(l-1))+2\n",
    "        elif la:\n",
    "            sn=pre_sn+pre_sn[0:ppp-1][::-1]\n",
    "            if int(sn)>=n:\n",
    "                n=int(sn)\n",
    "            else:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp-1][::-1])\n",
    "        else:\n",
    "            sn=pre_sn+pre_sn[0:ppp][::-1]\n",
    "            if int(sn)>=n:\n",
    "                n=int(sn)\n",
    "            else:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp][::-1])\n",
    "\n",
    "\n",
    "\n",
    "        while n <= R :\n",
    "            \n",
    "            if (ss:=str(n*n))==ss[::-1]: rs+=1\n",
    "\n",
    "            #寻找下一个n\n",
    "            sn = str(n)\n",
    "            pre_sn=sn[0:ppp]\n",
    "            if int(pre_sn[0])>2 or ((pre_sn[0])=='2' and int(pre_sn[1])>2):\n",
    "                n=(10**l)+1\n",
    "                l+=1\n",
    "                ppp=(l+1)//2\n",
    "                la=1-la\n",
    "            elif int(pre_sn[0])==1  and int(pre_sn[1])>1:\n",
    "                n=2*(10**(l-1))+2\n",
    "            elif la:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp-1][::-1])\n",
    "            else:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp][::-1])\n",
    "        return rs       \n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        def check(num):\n",
    "            num = int(int(num) ** 2)\n",
    "            if num > num1:\n",
    "                return 2\n",
    "            if num < num0:\n",
    "                return 1\n",
    "            num = str(num)\n",
    "            i = 0\n",
    "            j = len(num) - 1\n",
    "            while i < j:\n",
    "                if num[i] != num[j]:\n",
    "                    return 1\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            \n",
    "            return 0\n",
    "        num0 = int(left)\n",
    "        num1 = int(right)\n",
    "\n",
    "        sqrt0 = int(num0**0.5)\n",
    "        if int(sqrt0) != sqrt0:\n",
    "            sqrt0 += 1\n",
    "        sqrt1 = int(num1**0.5)\n",
    "        length0 = 0\n",
    "        t = sqrt0\n",
    "        while t:\n",
    "            length0 += 1\n",
    "            t //= 10\n",
    "        length1 = 0\n",
    "        t = sqrt1\n",
    "        while t:\n",
    "            length1 += 1\n",
    "            t //= 10\n",
    "\n",
    "        ans = 0\n",
    "        flag = True\n",
    "        for i in range(int(10**(length0//2-1)), min(int(10**(length1//2+1)), 20002)):\n",
    "            s = str(i)\n",
    "            if flag:\n",
    "                t0 = s + s[::-1]\n",
    "                tmp = check(t0)\n",
    "                if tmp == 0:\n",
    "                    ans += 1\n",
    "                elif tmp == 2:\n",
    "                    flag = False\n",
    "            t1 = s + s[:-1][::-1]\n",
    "            tmp = check(t1)\n",
    "            if tmp == 0:\n",
    "                ans += 1\n",
    "            elif tmp == 2:\n",
    "                break\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        L=ceil(pow(int(left),0.5))\n",
    "        R=floor(pow(int(right),0.5))\n",
    "        rs=0\n",
    "\n",
    "        if L<101:\n",
    "\n",
    "            for n in range(L,min(R+1,23)):\n",
    "                if n in (0,1,2,3,11,22):\n",
    "                    rs+=1\n",
    "\n",
    "        if R<=100: return rs            \n",
    "\n",
    "        \n",
    "        n=max(101,L)\n",
    "\n",
    "\n",
    "        # 确定首个回文数\n",
    "        sn = str(n)\n",
    "        l=len(sn)\n",
    "        ppp=(l+1)//2\n",
    "        la=l%2     \n",
    "        pre_sn=sn[0:ppp]   # 如果 la=1,说明pre_sn的最后一位是共有位，否则为对称位。\n",
    "        if int(pre_sn[0])>2 or ((pre_sn[0])=='2' and int(pre_sn[1])>2):\n",
    "            n=(10**l)+1\n",
    "            l+=1\n",
    "            ppp=(l+1)//2\n",
    "            la=1-la\n",
    "        elif int(pre_sn[0])==1  and int(pre_sn[1])>2:\n",
    "            n=2*(10**(l-1))+2\n",
    "        elif la:\n",
    "            sn=pre_sn+pre_sn[0:ppp-1][::-1]\n",
    "            if int(sn)>=n:\n",
    "                n=int(sn)\n",
    "            else:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp-1][::-1])\n",
    "        else:\n",
    "            sn=pre_sn+pre_sn[0:ppp][::-1]\n",
    "            if int(sn)>=n:\n",
    "                n=int(sn)\n",
    "            else:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp][::-1])\n",
    "\n",
    "\n",
    "\n",
    "        while n <= R :\n",
    "            \n",
    "            if (ss:=str(n*n))==ss[::-1]: rs+=1\n",
    "\n",
    "            #寻找下一个n\n",
    "            sn = str(n)\n",
    "            pre_sn=sn[0:ppp]\n",
    "            if int(pre_sn[0])>2 or ((pre_sn[0])=='2' and int(pre_sn[1])>2):\n",
    "                n=(10**l)+1\n",
    "                l+=1\n",
    "                ppp=(l+1)//2\n",
    "                la=1-la\n",
    "            elif int(pre_sn[0])==1  and int(pre_sn[1])>1:\n",
    "                n=2*(10**(l-1))+2\n",
    "            elif la:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp-1][::-1])\n",
    "            else:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp][::-1])\n",
    "        return rs       \n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "\n",
    "\n",
    "        L, R = int(left), int(right)\n",
    "\n",
    "        MAGIC = 100000\n",
    "        res = 0\n",
    "\n",
    "        def isparlindrome(x):\n",
    "            def reverse(x):\n",
    "                res = 0\n",
    "                while x:\n",
    "                    res = res * 10 + x % 10\n",
    "                    x //= 10\n",
    "                return res\n",
    "            return x == reverse(x)\n",
    "\n",
    "        \n",
    "        for k in range(MAGIC):\n",
    "            s = str(k)\n",
    "            t = s + s[-2::-1]\n",
    "            v = int(t) ** 2\n",
    "            if v > R:break\n",
    "            if v >= L and isparlindrome(v):\n",
    "                res += 1\n",
    "        \n",
    "        for k in range(MAGIC):\n",
    "            s = str(k)\n",
    "            t = s + s[::-1]\n",
    "            v = int(t) ** 2\n",
    "            if v > R: break\n",
    "            if v >= L and isparlindrome(v):\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        L = int(left)\n",
    "        R = int(right)\n",
    "        MAGIC = 100000\n",
    "        ans = 0\n",
    "\n",
    "        # 枚举奇数长度的回文数\n",
    "        for k in range(MAGIC):\n",
    "            s = str(k)\n",
    "            t = s + s[-2::-1]\n",
    "            v = int(t)**2\n",
    "            if v > R: break\n",
    "            if v >= L and str(v) == str(v)[::-1]: ans += 1\n",
    "\n",
    "        # 枚举偶数长度的回文数\n",
    "        for k in range(MAGIC):\n",
    "            s = str(k)\n",
    "            t = s + s[::-1]\n",
    "            v = int(t)**2\n",
    "            if v > R: break\n",
    "            if v >= L and str(v) == str(v)[::-1]: ans += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        L=ceil(pow(int(left),0.5))\n",
    "        R=floor(pow(int(right),0.5))\n",
    "        rs=0\n",
    "\n",
    "        if L<23:\n",
    "            for n in range(L,min(R+1,23)):\n",
    "                if n in (0,1,2,3,11,22):\n",
    "                    rs+=1\n",
    "\n",
    "        n=max(100,L)\n",
    "\n",
    "        # 确定首个回文数\n",
    "        sn = str(n)\n",
    "        l=len(sn)\n",
    "        ppp=(l+1)//2\n",
    "        la=l%2     \n",
    "        pre_sn=sn[0:ppp]   # 如果 la=1,说明pre_sn的最后一位是共有位，否则为对称位。\n",
    "        \n",
    "        if int(pre_sn[0])>2 or ((pre_sn[0])=='2' and int(pre_sn[1])>2):\n",
    "            n=(10**l)+1\n",
    "        elif int(pre_sn[0])==1  and int(pre_sn[1])>2:\n",
    "            n=2*(10**(l-1))+2\n",
    "        elif la:\n",
    "            sn=pre_sn+pre_sn[0:ppp-1][::-1]\n",
    "            print(sn)\n",
    "            if int(sn)>=n:\n",
    "                n=int(sn)\n",
    "            else:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp-1][::-1])\n",
    "        else:\n",
    "            sn=pre_sn+pre_sn[0:ppp][::-1]\n",
    "            if int(sn)>=n:\n",
    "                n=int(sn)\n",
    "            else:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp][::-1])\n",
    "\n",
    "        while n <= R :\n",
    "            \n",
    "            if (ss:=str(n*n))==ss[::-1]: rs+=1\n",
    "\n",
    "            #寻找下一个n\n",
    "            sn = str(n)\n",
    "            l=len(sn)\n",
    "            ppp=(l+1)//2\n",
    "            la=l%2     \n",
    "            pre_sn=sn[0:ppp]\n",
    "\n",
    "\n",
    "            if int(pre_sn[0])>2 or ((pre_sn[0])=='2' and int(pre_sn[1])>2):\n",
    "                n=(10**l)+1\n",
    "            elif int(pre_sn[0])==1  and int(pre_sn[1])>1:\n",
    "                n=2*(10**(l-1))+2\n",
    "            elif la:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp-1][::-1])\n",
    "            else:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp][::-1])\n",
    "        return rs       \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "               \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        count = 0\n",
    "        L = int(left)\n",
    "        R = int(right)\n",
    "\n",
    "        def check(num):\n",
    "            if 0 <= num < 10:\n",
    "                return True\n",
    "            numm = num\n",
    "            res = 0\n",
    "            while num != 0:\n",
    "                res, num = 10 * res + num % 10, num // 10\n",
    "            return res == numm\n",
    "        \n",
    "        # ranging from 1 to 10\n",
    "        for i in range(1, 10):\n",
    "            if L <= i ** 2 <= R and check(i ** 2):\n",
    "                count += 1\n",
    "\n",
    "        # ranging from 10 to 10000 \n",
    "        for ii in range(10000):\n",
    "            # even\n",
    "            i = str(ii)\n",
    "            tar_even = int(i + i[::-1])\n",
    "            tar_even **= 2\n",
    "            if L <= tar_even <= R and check(tar_even):\n",
    "                count += 1\n",
    "            # odd\n",
    "            for j in range(10):\n",
    "                tar_odd = int(i + str(j) + i[::-1])\n",
    "                tar_odd **= 2\n",
    "                if L <= tar_odd <= R and check(tar_odd):\n",
    "                    count += 1  \n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "#         L=ceil(pow(int(left),0.5))\n",
    "#         R=floor(pow(int(right),0.5))\n",
    "#         rs=0\n",
    "\n",
    "#         if L<23:\n",
    "#             for n in range(L,min(R+1,23)):\n",
    "#                 if n in (0,1,2,3,11,22):\n",
    "#                     rs+=1\n",
    "\n",
    "#         n=max(101,L)\n",
    "\n",
    "#         # 确定首个回文数\n",
    "#         sn = str(n)\n",
    "#         l=len(sn)\n",
    "#         ppp=(l+1)//2\n",
    "#         la=l%2     \n",
    "#         pre_sn=sn[0:ppp]   # 如果 la=1,说明pre_sn的最后一位是共有位，否则为对称位。\n",
    "#         if int(pre_sn[0])>2 or ((pre_sn[0])=='2' and int(pre_sn[1])>2):\n",
    "#             n=(10**l)+1\n",
    "#             l+=1\n",
    "#             ppp=(l+1)//2\n",
    "#             la=1-la\n",
    "#         elif int(pre_sn[0])==1  and int(pre_sn[1])>2:\n",
    "#             n=2*(10**(l-1))+2\n",
    "#         elif la:\n",
    "#             sn=pre_sn+pre_sn[0:ppp-1][::-1]\n",
    "#             if int(sn)>=n:\n",
    "#                 n=int(sn)\n",
    "#             else:\n",
    "#                 pre_sn=str(int(pre_sn)+1)\n",
    "#                 n=int(pre_sn+pre_sn[0:ppp-1][::-1])\n",
    "#         else:\n",
    "#             sn=pre_sn+pre_sn[0:ppp][::-1]\n",
    "#             if int(sn)>=n:\n",
    "#                 n=int(sn)\n",
    "#             else:\n",
    "#                 pre_sn=str(int(pre_sn)+1)\n",
    "#                 n=int(pre_sn+pre_sn[0:ppp][::-1])\n",
    "\n",
    "\n",
    "\n",
    "#         while n <= R :\n",
    "            \n",
    "#             if (ss:=str(n*n))==ss[::-1]: rs+=1\n",
    "\n",
    "#             #寻找下一个n\n",
    "#             sn = str(n)\n",
    "#             pre_sn=sn[0:ppp]\n",
    "#             if int(pre_sn[0])>2 or ((pre_sn[0])=='2' and int(pre_sn[1])>2):\n",
    "#                 n=(10**l)+1\n",
    "#                 l+=1\n",
    "#                 ppp=(l+1)//2\n",
    "#                 la=1-la\n",
    "#             elif int(pre_sn[0])==1  and int(pre_sn[1])>1:\n",
    "#                 n=2*(10**(l-1))+2\n",
    "#             elif la:\n",
    "#                 pre_sn=str(int(pre_sn)+1)\n",
    "#                 n=int(pre_sn+pre_sn[0:ppp-1][::-1])\n",
    "#             else:\n",
    "#                 pre_sn=str(int(pre_sn)+1)\n",
    "#                 n=int(pre_sn+pre_sn[0:ppp][::-1])\n",
    "#         return rs       \n",
    "            \n",
    "\n",
    "\n",
    "def dfs(n, c):\n",
    "    if c == 0:\n",
    "        s = int(n) ** 2\n",
    "        if str(s) == str(s)[::-1]:\n",
    "            res.append(s)\n",
    "        return\n",
    "    if c == i:\n",
    "        r = range(1, 3)\n",
    "    else:\n",
    "        r = range(3)\n",
    "    for j in r:\n",
    "        dfs(n + str(j), c - 1)\n",
    "\n",
    "res = []\n",
    "for i in range(1, 10):\n",
    "    dfs(\"\", i)\n",
    "res.insert(2, 9)\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        return bisect.bisect_right(res, int(right)) - bisect.bisect_left(res, int(left))\n",
    "               \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        def check(num):\n",
    "            num = int(int(num) ** 2)\n",
    "            if num < num0 or num > num1:\n",
    "                return False\n",
    "            num = str(num)\n",
    "            i = 0\n",
    "            j = len(num) - 1\n",
    "            while i < j:\n",
    "                if num[i] != num[j]:\n",
    "                    return False\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            \n",
    "            return True\n",
    "        num0 = int(left)\n",
    "        num1 = int(right)\n",
    "\n",
    "        sqrt0 = int(num0**0.5)\n",
    "        if int(sqrt0) != sqrt0:\n",
    "            sqrt0 += 1\n",
    "        sqrt1 = int(num1**0.5)\n",
    "        length0 = 0\n",
    "        t = sqrt0\n",
    "        while t:\n",
    "            length0 += 1\n",
    "            t //= 10\n",
    "        length1 = 0\n",
    "        t = sqrt1\n",
    "        while t:\n",
    "            length1 += 1\n",
    "            t //= 10\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(int(10**(length0//2-1)), int(10**(length1//2+1))):\n",
    "            s = str(i)\n",
    "            t0 = s + s[::-1]\n",
    "            if check(t0):\n",
    "                ans += 1\n",
    "            t1 = s + s[:-1][::-1]\n",
    "            if check(t1):\n",
    "                ans += 1\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        L=ceil(pow(int(left),0.5))\n",
    "        R=floor(pow(int(right),0.5))\n",
    "        rs=0\n",
    "\n",
    "        if L<23:\n",
    "            for n in range(L,min(R+1,23)):\n",
    "                if n in (0,1,2,3,11,22):\n",
    "                    rs+=1\n",
    "\n",
    "        # print(rs)\n",
    "        n=max(100,L)\n",
    "        # print(n)\n",
    "        # 确定首个回文数\n",
    "        sn = str(n)\n",
    "        l=len(sn)\n",
    "        ppp=(l+1)//2\n",
    "        la=l%2     \n",
    "        pre_sn=sn[0:ppp]   # 如果 la=1,说明pre_sn的最后一位是共有位，否则为对称位。\n",
    "        \n",
    "        if int(pre_sn[0])>2 or ((pre_sn[0])=='2' and int(pre_sn[1])>2):\n",
    "            n=(10**l)+1\n",
    "        elif int(pre_sn[0])==1  and int(pre_sn[1])>2:\n",
    "            n=2*(10**(l-1))+2\n",
    "        elif la:\n",
    "            # print('sn=',sn,'pre_sn=',pre_sn)\n",
    "            # print(pre_sn,'aaaa',pre_sn[0:ppp-1][::-1])\n",
    "            sn=pre_sn+pre_sn[0:ppp-1][::-1]\n",
    "            print(sn)\n",
    "            if int(sn)>=n:\n",
    "                n=int(sn)\n",
    "            else:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp-1][::-1])\n",
    "        else:\n",
    "            sn=pre_sn+pre_sn[0:ppp][::-1]\n",
    "            if int(sn)>=n:\n",
    "                n=int(sn)\n",
    "            else:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp][::-1])\n",
    "\n",
    "        # print(n)\n",
    "        while n <= R :\n",
    "            if (ss:=str(n*n))==ss[::-1]: rs+=1\n",
    "\n",
    "            #寻找下一个n\n",
    "            sn = str(n)\n",
    "            l=len(sn)\n",
    "            ppp=(l+1)//2\n",
    "            la=l%2     \n",
    "            pre_sn=sn[0:ppp]\n",
    "\n",
    "\n",
    "            if int(pre_sn[0])>2 or ((pre_sn[0])=='2' and int(pre_sn[1])>2):\n",
    "                n=(10**l)+1\n",
    "            elif int(pre_sn[0])==1  and int(pre_sn[1])>2:\n",
    "                n=2*(10**(l-1))+2\n",
    "            elif la:\n",
    "            \n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp-1][::-1])\n",
    "            else:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp][::-1])\n",
    "            # print(n)     \n",
    "        return rs       \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "               \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        L=ceil(pow(int(left),0.5))\n",
    "        R=floor(pow(int(right),0.5))\n",
    "        rs=0\n",
    "\n",
    "        if L<23:\n",
    "            for n in range(L,min(R+1,23)):\n",
    "                if n in (0,1,2,3,11,22):\n",
    "                    rs+=1\n",
    "\n",
    "        # print(rs)\n",
    "        n=max(100,L)\n",
    "        # print(n)\n",
    "        # 确定首个回文数\n",
    "        sn = str(n)\n",
    "        l=len(sn)\n",
    "        la=l%2     \n",
    "        pre_sn=sn[0:(l+1)//2]   # 如果 la=1,说明pre_sn的最后一位是共有位，否则为对称位。\n",
    "        \n",
    "        if int(pre_sn[0])>2 or ((pre_sn[0])=='2' and int(pre_sn[1])>2):\n",
    "            n=(10**l)+1\n",
    "        elif int(pre_sn[0])==1  and int(pre_sn[1])>2:\n",
    "            n=2*(10**(l-1))+2\n",
    "        elif la:\n",
    "            # print('sn=',sn,'pre_sn=',pre_sn)\n",
    "            # print(pre_sn,'aaaa',pre_sn[0:(l+1)//2-1][::-1])\n",
    "            sn=pre_sn+pre_sn[0:(l+1)//2-1][::-1]\n",
    "            print(sn)\n",
    "            if int(sn)>=n:\n",
    "                n=int(sn)\n",
    "            else:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:(l+1)//2-1][::-1])\n",
    "        else:\n",
    "            sn=pre_sn+pre_sn[0:(l+1)//2][::-1]\n",
    "            if int(sn)>=n:\n",
    "                n=int(sn)\n",
    "            else:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:(l+1)//2][::-1])\n",
    "\n",
    "        # print(n)\n",
    "        while n <= R :\n",
    "            if (ss:=str(n*n))==ss[::-1]: rs+=1\n",
    "\n",
    "            #寻找下一个n\n",
    "            sn = str(n)\n",
    "            l=len(sn)\n",
    "            la=l%2     \n",
    "            pre_sn=sn[0:(l+1)//2]\n",
    "\n",
    "\n",
    "            if int(pre_sn[0])>2 or ((pre_sn[0])=='2' and int(pre_sn[1])>2):\n",
    "                n=(10**l)+1\n",
    "            elif int(pre_sn[0])==1  and int(pre_sn[1])>2:\n",
    "                n=2*(10**(l-1))+2\n",
    "            elif la:\n",
    "            \n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:(l+1)//2-1][::-1])\n",
    "            else:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:(l+1)//2][::-1])\n",
    "            # print(n)     \n",
    "        return rs       \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "               \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        def isPalindrome(x):\n",
    "            offset = 1\n",
    "            while x//offset >= 10:\n",
    "                offset *= 10\n",
    "            while x!=0:\n",
    "                if x//offset != x%10:\n",
    "                    return False\n",
    "                x = x%offset//10\n",
    "                offset //= 100\n",
    "            return True\n",
    "        def evenEnlarge(seed):\n",
    "            ans = seed\n",
    "            while seed!=0:\n",
    "                ans = ans*10 + seed%10\n",
    "                seed //= 10\n",
    "            return ans\n",
    "        def oddEnlarge(seed):\n",
    "            ans = seed\n",
    "            seed //= 10\n",
    "            while seed!=0:\n",
    "                ans = ans*10 + seed%10\n",
    "                seed //= 10\n",
    "            return ans\n",
    "        def check(ans,l,r):\n",
    "            return ans>=l and ans<=r and isPalindrome(ans)\n",
    "        l = float(left)\n",
    "        r = float(right)\n",
    "        limit = sqrt(r)\n",
    "        seed = 1\n",
    "        num = 0\n",
    "        ans = 0\n",
    "        while num<limit:\n",
    "            num = evenEnlarge(seed)\n",
    "            if check(num*num,l,r):\n",
    "                ans += 1\n",
    "            num = oddEnlarge(seed)\n",
    "            if check(num*num,l,r):\n",
    "                ans += 1\n",
    "            seed += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\r\n",
    "class Solution:\r\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\r\n",
    "        _L=int(left)\r\n",
    "        _R=int(right)\r\n",
    "        _l=int(math.sqrt(_L))\r\n",
    "        _r=int(math.sqrt(_R))\r\n",
    "        s_l=len(str(_l))\r\n",
    "        \r\n",
    "        def is_p(x:int):\r\n",
    "            y=x\r\n",
    "            z=0\r\n",
    "            while x>0:\r\n",
    "                z=z*10+x%10\r\n",
    "                x//=10\r\n",
    "            return z==y\r\n",
    "\r\n",
    "        ret=0\r\n",
    "        while True:\r\n",
    "            half=(s_l+1)//2\r\n",
    "            for i in range(10**(half-1),10**half):\r\n",
    "                j=i\r\n",
    "                if s_l%2:\r\n",
    "                    i//=10\r\n",
    "                while i>0:\r\n",
    "                    j=j*10+i%10\r\n",
    "                    i//=10\r\n",
    "                if j<_l:\r\n",
    "                    continue\r\n",
    "                jj=j**2\r\n",
    "                if jj>_R:\r\n",
    "                    return ret\r\n",
    "                if is_p(jj):\r\n",
    "                    ret+=1\r\n",
    "            s_l+=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        L=ceil(pow(int(left),0.5))\n",
    "        R=floor(pow(int(right),0.5))\n",
    "        rs=0\n",
    "\n",
    "        if L<23:\n",
    "            for n in range(L,min(R+1,23)):\n",
    "                if n in (0,1,2,3,11,22):\n",
    "                    rs+=1\n",
    "\n",
    "        n=max(100,L)\n",
    "\n",
    "        # 确定首个回文数\n",
    "        sn = str(n)\n",
    "        l=len(sn)\n",
    "        ppp=(l+1)//2\n",
    "        la=l%2     \n",
    "        pre_sn=sn[0:ppp]   # 如果 la=1,说明pre_sn的最后一位是共有位，否则为对称位。\n",
    "        \n",
    "        if int(pre_sn[0])>2 or ((pre_sn[0])=='2' and int(pre_sn[1])>2):\n",
    "            n=(10**l)+1\n",
    "        elif int(pre_sn[0])==1  and int(pre_sn[1])>2:\n",
    "            n=2*(10**(l-1))+2\n",
    "        elif la:\n",
    "            sn=pre_sn+pre_sn[0:ppp-1][::-1]\n",
    "            print(sn)\n",
    "            if int(sn)>=n:\n",
    "                n=int(sn)\n",
    "            else:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp-1][::-1])\n",
    "        else:\n",
    "            sn=pre_sn+pre_sn[0:ppp][::-1]\n",
    "            if int(sn)>=n:\n",
    "                n=int(sn)\n",
    "            else:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp][::-1])\n",
    "\n",
    "\n",
    "        l=len(str(n))\n",
    "        ppp=(l+1)//2\n",
    "        la=l%2     \n",
    "\n",
    "        while n <= R :\n",
    "            \n",
    "            if (ss:=str(n*n))==ss[::-1]: rs+=1\n",
    "\n",
    "            #寻找下一个n\n",
    "            sn = str(n)\n",
    "            # l=len(sn)\n",
    "            # ppp=(l+1)//2\n",
    "            # la=l%2     \n",
    "            pre_sn=sn[0:ppp]\n",
    "\n",
    "\n",
    "            if int(pre_sn[0])>2 or ((pre_sn[0])=='2' and int(pre_sn[1])>2):\n",
    "                n=(10**l)+1\n",
    "                l+=1\n",
    "                ppp=(l+1)//2\n",
    "                la=1-la\n",
    "            elif int(pre_sn[0])==1  and int(pre_sn[1])>1:\n",
    "                n=2*(10**(l-1))+2\n",
    "            elif la:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp-1][::-1])\n",
    "            else:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp][::-1])\n",
    "        return rs       \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "               \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def supperpalindromes10000(self, lower, upper) -> List[int]:\n",
    "        ret = 0\n",
    "        lower_s = int(math.sqrt(lower))\n",
    "        upper_s = int(math.sqrt(upper)) + 1\n",
    "        for i in range(lower_s, upper_s):\n",
    "            i2 = i**2\n",
    "            if i2 <= upper and i2 >= lower and self._check(i) and self._check(i2):\n",
    "                ret += 1\n",
    "        return ret\n",
    "\n",
    "    def _check(self, n: int) -> bool:\n",
    "        if n < 10:\n",
    "            return True\n",
    "        s = str(n)\n",
    "        l = len(s)\n",
    "        return s[:l//2] == s[-1:l//2-1:-1] if l % 2 == 0 else s[:l//2] == s[-1:l//2:-1]\n",
    "\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        lower, upper = int(left), int(right)\n",
    "        if upper < 10000:\n",
    "            return self.supperpalindromes10000(lower, upper)\n",
    "\n",
    "        left = int(math.sqrt(int(left)))\n",
    "        right = int(math.sqrt(int(right)))\n",
    "        ret = 0\n",
    "\n",
    "        def _halfen(s: int) -> int:\n",
    "            if s < 9:\n",
    "                return int(s)\n",
    "            n = len(str(s))//2\n",
    "            return int(s//(10**n))\n",
    "\n",
    "        def _padding(s: int) -> (int, int):\n",
    "            s1 = s\n",
    "            s0 = s\n",
    "            nums = []\n",
    "            while s0 > 0:\n",
    "                nums.append(s0 % 10)\n",
    "                s0 = s0//10\n",
    "            for i in nums[1:]:\n",
    "                s1 = s1*10 + i\n",
    "\n",
    "            s2 = s\n",
    "            for i in nums:\n",
    "                s2 = s2*10 + i\n",
    "            return (s1, s2)\n",
    "\n",
    "        right = _halfen(right*3)\n",
    "        left = _halfen(left/10)\n",
    "        for i in range(left, right+1):\n",
    "            s1, s2 = _padding(i)\n",
    "            s1, s2 = s1**2, s2**2\n",
    "            if s1 <= upper and s1 >= lower and self._check(s1):\n",
    "                ret += 1\n",
    "            if s2 <= upper and s2 >= lower and self._check(s2):\n",
    "                ret += 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        L=ceil(pow(int(left),0.5))\n",
    "        R=floor(pow(int(right),0.5))\n",
    "        rs=0\n",
    "\n",
    "        if L<23:\n",
    "            for n in range(L,min(R+1,23)):\n",
    "                if n in (0,1,2,3,11,22):\n",
    "                    rs+=1\n",
    "\n",
    "        n=max(100,L)\n",
    "\n",
    "        # 确定首个回文数\n",
    "        sn = str(n)\n",
    "        l=len(sn)\n",
    "        ppp=(l+1)//2\n",
    "        la=l%2     \n",
    "        pre_sn=sn[0:ppp]   # 如果 la=1,说明pre_sn的最后一位是共有位，否则为对称位。\n",
    "        \n",
    "        if int(pre_sn[0])>2 or ((pre_sn[0])=='2' and int(pre_sn[1])>2):\n",
    "            n=(10**l)+1\n",
    "            l+=1\n",
    "            ppp=(l+1)//2\n",
    "            la=1-la\n",
    "\n",
    "        elif int(pre_sn[0])==1  and int(pre_sn[1])>2:\n",
    "            n=2*(10**(l-1))+2\n",
    "        elif la:\n",
    "            sn=pre_sn+pre_sn[0:ppp-1][::-1]\n",
    "            print(sn)\n",
    "            if int(sn)>=n:\n",
    "                n=int(sn)\n",
    "            else:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp-1][::-1])\n",
    "        else:\n",
    "            sn=pre_sn+pre_sn[0:ppp][::-1]\n",
    "            if int(sn)>=n:\n",
    "                n=int(sn)\n",
    "            else:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp][::-1])\n",
    "\n",
    "\n",
    "        # l=len(str(n))\n",
    "        # ppp=(l+1)//2\n",
    "        # la=l%2     \n",
    "\n",
    "        while n <= R :\n",
    "            \n",
    "            if (ss:=str(n*n))==ss[::-1]: rs+=1\n",
    "\n",
    "            #寻找下一个n\n",
    "            sn = str(n)\n",
    "\n",
    "            pre_sn=sn[0:ppp]\n",
    "\n",
    "\n",
    "            if int(pre_sn[0])>2 or ((pre_sn[0])=='2' and int(pre_sn[1])>2):\n",
    "                n=(10**l)+1\n",
    "                l+=1\n",
    "                ppp=(l+1)//2\n",
    "                la=1-la\n",
    "            elif int(pre_sn[0])==1  and int(pre_sn[1])>1:\n",
    "                n=2*(10**(l-1))+2\n",
    "            elif la:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp-1][::-1])\n",
    "            else:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp][::-1])\n",
    "        return rs       \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "               \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 简要说明： 超级回文数的首位必定为1或4,它的开平方首（尾）位必定为1,2，第二位不超过3.\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        L=ceil(pow(int(left),0.5))\n",
    "        R=floor(pow(int(right),0.5))\n",
    "        rs=0\n",
    "\n",
    "        if L<101:\n",
    "            for n in range(L,min(R+1,23)):\n",
    "                if n in (0,1,2,3,11,22):\n",
    "                    rs+=1\n",
    "        if R<=100: return rs            \n",
    "\n",
    "\n",
    "        n=max(101,L)\n",
    "        # 确定进入循环的回文数\n",
    "        sn = str(n)\n",
    "        l=len(sn)\n",
    "        ppp=(l+1)//2\n",
    "        la=l%2     \n",
    "        pre_sn=sn[0:ppp]   # 如果 la=1,说明pre_sn的最后一位是共有位，否则为对称位。\n",
    "        if int(pre_sn[0])>2 or ((pre_sn[0])=='2' and int(pre_sn[1])>2):\n",
    "            n=(10**l)+1\n",
    "            l+=1\n",
    "            ppp=(l+1)//2\n",
    "            la=1-la\n",
    "        elif int(pre_sn[0])==1  and int(pre_sn[1])>2:\n",
    "            n=2*(10**(l-1))+2\n",
    "        elif la:\n",
    "            sn=pre_sn+pre_sn[0:ppp-1][::-1]\n",
    "            if int(sn)>=n:\n",
    "                n=int(sn)\n",
    "            else:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp-1][::-1])\n",
    "        else:\n",
    "            sn=pre_sn+pre_sn[0:ppp][::-1]\n",
    "            if int(sn)>=n:\n",
    "                n=int(sn)\n",
    "            else:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp][::-1])\n",
    "\n",
    "        #此时n为回文数\n",
    "\n",
    "        while n <= R :\n",
    "            \n",
    "            if (ss:=str(n*n))==ss[::-1]: rs+=1\n",
    "\n",
    "            #产生下一个回文数\n",
    "            sn = str(n)\n",
    "            pre_sn=sn[0:ppp]\n",
    "            if int(pre_sn[0])>2 or ((pre_sn[0])=='2' and int(pre_sn[1])>1): #首位小于3 并且 首两位小于23\n",
    "                n=(10**l)+1\n",
    "                l+=1\n",
    "                ppp=(l+1)//2\n",
    "                la=1-la\n",
    "            elif int(pre_sn[0])==1  and int(pre_sn[1])>1:      #11,12 打头符合，13不符合\n",
    "                n=2*(10**(l-1))+2\n",
    "            elif la:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp-1][::-1])\n",
    "            else:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp][::-1])\n",
    "        return rs       \n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\r\n",
    "class Solution:\r\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\r\n",
    "        _L=int(left)\r\n",
    "        _R=int(right)\r\n",
    "        magic=10**5\r\n",
    "        \r\n",
    "        def is_p(x:int):\r\n",
    "            y=x\r\n",
    "            z=0\r\n",
    "            while x>0:\r\n",
    "                z=z*10+x%10\r\n",
    "                x//=10\r\n",
    "            return y==z\r\n",
    "\r\n",
    "        ret=0\r\n",
    "        # odd\r\n",
    "        for i in range(magic):\r\n",
    "            j=i\r\n",
    "            i//=10\r\n",
    "            while i>0:\r\n",
    "                j=j*10+i%10\r\n",
    "                i//=10\r\n",
    "            jj=j*j\r\n",
    "            if jj<_L:\r\n",
    "                continue\r\n",
    "            if jj>_R:\r\n",
    "                break\r\n",
    "            if is_p(jj):\r\n",
    "                ret+=1\r\n",
    "\r\n",
    "        # even\r\n",
    "        for i in range(magic):\r\n",
    "            j=i\r\n",
    "            while i>0:\r\n",
    "                j=j*10+i%10\r\n",
    "                i//=10\r\n",
    "            jj=j*j\r\n",
    "            if jj<_L:\r\n",
    "                continue\r\n",
    "            if jj>_R:\r\n",
    "                break\r\n",
    "            if is_p(jj):\r\n",
    "                ret+=1\r\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 简要说明： 超级回文数的首位必定为1或4,它的开平方首（尾）位必定为1,2，第二位不超过3.\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        L=ceil(pow(int(left),0.5))\n",
    "        R=floor(pow(int(right),0.5))\n",
    "        rs=0\n",
    "\n",
    "        if L<101:\n",
    "\n",
    "            for n in range(L,min(R+1,23)):\n",
    "                if n in (0,1,2,3,11,22):\n",
    "                    rs+=1\n",
    "\n",
    "        if R<=100: return rs            \n",
    "\n",
    "        \n",
    "        n=max(101,L)\n",
    "\n",
    "\n",
    "        # 确定首个回文数\n",
    "        sn = str(n)\n",
    "        l=len(sn)\n",
    "        ppp=(l+1)//2\n",
    "        la=l%2     \n",
    "        pre_sn=sn[0:ppp]   # 如果 la=1,说明pre_sn的最后一位是共有位，否则为对称位。\n",
    "        if int(pre_sn[0])>2 or ((pre_sn[0])=='2' and int(pre_sn[1])>2):\n",
    "            n=(10**l)+1\n",
    "            l+=1\n",
    "            ppp=(l+1)//2\n",
    "            la=1-la\n",
    "        elif int(pre_sn[0])==1  and int(pre_sn[1])>2:\n",
    "            n=2*(10**(l-1))+2\n",
    "        elif la:\n",
    "            sn=pre_sn+pre_sn[0:ppp-1][::-1]\n",
    "            if int(sn)>=n:\n",
    "                n=int(sn)\n",
    "            else:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp-1][::-1])\n",
    "        else:\n",
    "            sn=pre_sn+pre_sn[0:ppp][::-1]\n",
    "            if int(sn)>=n:\n",
    "                n=int(sn)\n",
    "            else:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp][::-1])\n",
    "\n",
    "        #此时n为回文数\n",
    "\n",
    "        while n <= R :\n",
    "            \n",
    "            if (ss:=str(n*n))==ss[::-1]: rs+=1\n",
    "\n",
    "            #寻找下一个n\n",
    "            sn = str(n)\n",
    "            pre_sn=sn[0:ppp]\n",
    "            if int(pre_sn[0])>2 or ((pre_sn[0])=='2' and int(pre_sn[1])>2):\n",
    "                n=(10**l)+1\n",
    "                l+=1\n",
    "                ppp=(l+1)//2\n",
    "                la=1-la\n",
    "            elif int(pre_sn[0])==1  and int(pre_sn[1])>1:\n",
    "                n=2*(10**(l-1))+2\n",
    "            elif la:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp-1][::-1])\n",
    "            else:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp][::-1])\n",
    "        return rs       \n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def supperpalindromes10000(self, lower, upper) -> List[int]:\n",
    "        ret = 0\n",
    "        lower_s = int(math.sqrt(lower))\n",
    "        upper_s = int(math.sqrt(upper)) + 1\n",
    "        for i in range(lower_s, upper_s):\n",
    "            i2 = i**2\n",
    "            if i2 <= upper and i2 >= lower and self._check(i) and self._check(i2):\n",
    "                ret += 1\n",
    "        return ret\n",
    "\n",
    "    def _check(self, n: int) -> bool:\n",
    "        if n < 10:\n",
    "            return True\n",
    "        s = str(n)\n",
    "        l = len(s)\n",
    "        return s[:l//2] == s[-1:l//2-1:-1] if l % 2 == 0 else s[:l//2] == s[-1:l//2:-1]\n",
    "\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        lower, upper = int(left), int(right)\n",
    "        if upper < 10000:\n",
    "            return self.supperpalindromes10000(lower, upper)\n",
    "\n",
    "        left = int(math.sqrt(int(left)))\n",
    "        right = int(math.sqrt(int(right)))\n",
    "        ret = 0\n",
    "\n",
    "        def _halfen(s: int) -> int:\n",
    "            if s < 9:\n",
    "                return int(s)\n",
    "            n = len(str(s))//2\n",
    "            return int(s//(10**n))\n",
    "\n",
    "        def _padding(s: int) -> (int, int):\n",
    "            s1 = s\n",
    "            s0 = s\n",
    "            nums = []\n",
    "            while s0 > 0:\n",
    "                nums.append(s0 % 10)\n",
    "                s0 = s0//10\n",
    "            for i in nums[1:]:\n",
    "                s1 = s1*10 + i\n",
    "\n",
    "            s2 = s\n",
    "            for i in nums:\n",
    "                s2 = s2*10 + i\n",
    "            return (s1, s2)\n",
    "\n",
    "        right = _halfen(right*3)\n",
    "        left = _halfen(left/10)\n",
    "        for i in range(left, right+1):\n",
    "            s1, s2 = _padding(i)\n",
    "            s1, s2 = s1**2, s2**2\n",
    "            if s1 <= upper and s1 >= lower and self._check(s1):\n",
    "                ret += 1\n",
    "            if s2 <= upper and s2 >= lower and self._check(s2):\n",
    "                ret += 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 简要说明： 超级回文数的首位必定为1或4,它的开平方首（尾）位必定为1,2，第二位不超过3.\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        L=ceil(pow(int(left),0.5))\n",
    "        R=floor(pow(int(right),0.5))\n",
    "        rs=0\n",
    "\n",
    "        if L<101:\n",
    "            for n in range(L,min(R+1,23)):\n",
    "                if n in (0,1,2,3,11,22):\n",
    "                    rs+=1\n",
    "        if R<=100: return rs            \n",
    "\n",
    "\n",
    "        n=max(101,L)\n",
    "        # 确定进入循环的回文数\n",
    "        sn = str(n)\n",
    "        l=len(sn)\n",
    "        ppp=(l+1)//2\n",
    "        la=l%2     \n",
    "        pre_sn=sn[0:ppp]   # 如果 la=1,说明pre_sn的最后一位是共有位，否则为对称位。\n",
    "        if int(pre_sn[0])>2 or ((pre_sn[0])=='2' and int(pre_sn[1])>2):\n",
    "            n=(10**l)+1\n",
    "            l+=1\n",
    "            ppp=(l+1)//2\n",
    "            la=1-la\n",
    "        elif int(pre_sn[0])==1  and int(pre_sn[1])>2:\n",
    "            n=2*(10**(l-1))+2\n",
    "        elif la:\n",
    "            sn=pre_sn+pre_sn[0:ppp-1][::-1]\n",
    "            if int(sn)>=n:\n",
    "                n=int(sn)\n",
    "            else:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp-1][::-1])\n",
    "        else:\n",
    "            sn=pre_sn+pre_sn[0:ppp][::-1]\n",
    "            if int(sn)>=n:\n",
    "                n=int(sn)\n",
    "            else:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp][::-1])\n",
    "\n",
    "        #此时n为回文数\n",
    "\n",
    "        while n <= R :\n",
    "            \n",
    "            if (ss:=str(n*n))==ss[::-1]: rs+=1\n",
    "\n",
    "            #产生下一个回文数\n",
    "            sn = str(n)\n",
    "            pre_sn=sn[0:ppp]\n",
    "            if int(pre_sn[0])>2 or ((pre_sn[0])=='2' and int(pre_sn[1])>1): #首位小于3 并且 首两位小于23\n",
    "                n=(10**l)+1\n",
    "                l+=1\n",
    "                ppp=(l+1)//2\n",
    "                la=1-la\n",
    "            elif int(pre_sn[0])==1  and int(pre_sn[1])>1:      #11,12 打头符合，13不符合\n",
    "                n=2*(10**(l-1))+2\n",
    "            elif la:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp-1][::-1])\n",
    "            else:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp][::-1])\n",
    "        return rs       \n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 简要说明： 超级回文数的首位必定为1或4,它的开平方首（尾）位必定为1,2，第二位不超过3.\n",
    "class Solution:\n",
    "    def superpalindromesInRange(self, left: str, right: str) -> int:\n",
    "        L=ceil(pow(int(left),0.5))\n",
    "        R=floor(pow(int(right),0.5))\n",
    "        rs=0\n",
    "\n",
    "        if L<101:\n",
    "            for n in range(L,min(R+1,23)):\n",
    "                if n in (0,1,2,3,11,22):\n",
    "                    rs+=1\n",
    "        if R<=100: return rs            \n",
    "\n",
    "\n",
    "        n=max(101,L)\n",
    "        # 确定进入循环的回文数\n",
    "        sn = str(n)\n",
    "        l=len(sn)\n",
    "        ppp=(l+1)//2\n",
    "        la=l%2     \n",
    "        pre_sn=sn[0:ppp]   # 如果 la=1,说明pre_sn的最后一位是共有位，否则为对称位。\n",
    "        if int(pre_sn[0])>2 or ((pre_sn[0])=='2' and int(pre_sn[1])>2):\n",
    "            n=(10**l)+1\n",
    "            l+=1\n",
    "            ppp=(l+1)//2\n",
    "            la=1-la\n",
    "        elif int(pre_sn[0])==1  and int(pre_sn[1])>2:\n",
    "            n=2*(10**(l-1))+2\n",
    "        elif la:\n",
    "            sn=pre_sn+pre_sn[0:ppp-1][::-1]\n",
    "            if int(sn)>=n:\n",
    "                n=int(sn)\n",
    "            else:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp-1][::-1])\n",
    "        else:\n",
    "            sn=pre_sn+pre_sn[0:ppp][::-1]\n",
    "            if int(sn)>=n:\n",
    "                n=int(sn)\n",
    "            else:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp][::-1])\n",
    "\n",
    "        #此时n为回文数\n",
    "\n",
    "        while n <= R :\n",
    "            \n",
    "            if (ss:=str(n*n))==ss[::-1]: rs+=1\n",
    "\n",
    "            #产生下一个回文数\n",
    "            sn = str(n)\n",
    "            pre_sn=sn[0:ppp]\n",
    "            if int(pre_sn[0])>2 or ((pre_sn[0])=='2' and int(pre_sn[1])>1): #首位小于3 并且 首两位小于23\n",
    "                n=(10**l)+1\n",
    "                l+=1\n",
    "                ppp=(l+1)//2\n",
    "                la=1-la\n",
    "            elif int(pre_sn[0])==1  and int(pre_sn[1])>1:      #11,12 打头符合，13不符合\n",
    "                n=2*(10**(l-1))+2\n",
    "            elif la:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp-1][::-1])\n",
    "            else:\n",
    "                pre_sn=str(int(pre_sn)+1)\n",
    "                n=int(pre_sn+pre_sn[0:ppp][::-1])\n",
    "        return rs       \n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
